Редовна езикова дефиниция на теорията на автоматите. Методи за определяне на обикновени езици. Азбука, дума, език

Лабораторна работа №3

Разработването на лексикален анализатор е доста просто, ако се използва теорията на редовните езици и крайните автомати. В рамките на тази теория класове лексеми от един и същи тип се считат за формални езици (езика на идентификаторите, езика на константите и т.н.), чийто набор от изречения се описва с помощта на съответната генеративна граматика. Освен това тези езици са толкова прости, че са генерирани от най-простата граматика - обикновената граматика.

Определение 1. генеративна граматика G = , чиито правила имат вида: A::=aB или C::=b, където A, B, C Є N; a, b Є Т се нарича редовен (автоматичен).

Езикът L (G), генериран от автоматна граматика, се нарича автоматен (регулярен) език или език с краен брой състояния.

Пример 1. Клас идентификатори, ако идентификаторът е последователност, състояща се от букви и цифри и първият знак на идентификатора може да бъде само буква, се описва от следната генеративна регулярна граматика G = , при което

N= (I, K), T = (b, c), S=(I),

P = ( 1. I::= b

Тук b, c са обобщени крайни символи за обозначаване съответно на букви и цифри.

Процесът на генериране на идентификатора „bbcbc“ се описва със следната последователност от замествания

I => bbc => bbc => bbcK => bbcbK => bbcbc

Основната задача на LA обаче не е генерирането на лексикални единици, а тяхното разпознаване. Математическият модел на процеса на разпознаване на нормален език е изчислително устройство, наречено краен автомат (FA). Терминът "краен" подчертава, че изчислителното устройство има фиксирано и ограничено количество памет и обработва последователност от входни символи, принадлежащи към някакъв краен набор. Има различни видове KA, ако изходната функция KA (резултат от работа) е само индикация дали входната последователност от символи е приемлива или не, такава KA се нарича окончателен преобразувател.

Определение 2. Следните пет се наричат ​​краен автомат:

А = , където V = (a 1 , a 2 , …, a m ) – входна азбука (краен набор от символи);

Q = (q 0 , q 1 , …, q n -1 ) – азбука на състоянията (краен набор от символи);

δ: Q ×V →Q – преходна функция;

q 0 Є Q – начално състояние на крайния автомат;

F Є Q – множество от крайни състояния.

Схема на работа на космическия кораб.

Има безкрайна лента, разделена на клетки, всяка от които може да съдържа един символ от V. На лентата е записана веригата α Є V*. Клетките отляво и отдясно на веригата са празни. Има устройство за крайно управление (FCU) с четяща глава, която може последователно да чете знаци от лентата, движейки се по лентата отляво надясно. В този случай контролният блок може да бъде във всяко едно състояние от Q. Контролният блок винаги започва своята работа в първоначалното състояние q 0 и завършва в едно от крайните състояния F. Всеки път, преминавайки към нова клетка на лента, контролният блок преминава в ново състояние в съответствие с функцията δ.

Преходната функция на космическия кораб може да бъде представена по следните начини:

· Набор от екипи;

· Диаграма на състоянието;

· Преходна маса.

Командата на държавната машина е написана по следния начин:

(q i, a j) → q k, където q i, q k Є Q; a j Є V.

Тази команда означава, че крайната машина е в състояние q i, чете символа a j от лентата и преминава в състояние q k.

Графично командата е представена като дъга на графика, преминаваща от връх q i до връх q k и маркирана със символа a j от въведената азбука:

Графичното представяне на цялото преобразуване δ се нарича диаграма на състоянието на краен автомат.

Ако космическият кораб се окаже в ситуация (q i, a j), която не е лявата страна на никоя команда, тогава той спира. Ако контролният блок преброи всички символи на веригата α, записани на лентата, и в същото време премине към крайното състояние q r Є F, тогава те казват, че веригата α е разрешена от крайната машина.

Преходната таблица на космическия кораб се изгражда по следния начин: матричните колони съответстват на символи от входната азбука, редовете съответстват на символи от азбуката на състоянието, а матричните елементи съответстват на състоянията, в които преминава космическият кораб за дадена комбинация от входен символ и държавен символ.

Нека регулярна граматика G = , чиито правила имат формата: A i::= a j A k или A i::= a j, където A i, A k Є N и a j Є T.

Тогава крайният автомат A = , допускащ същия език, който генерира регулярната граматика G, се конструира, както следва:

2) Q = N U (Z), Z N и Z T, Z е крайното състояние на космическия кораб;

5) Преобразуването δ се конструира във формата:

· Всяко правило за заместване в граматиката G на формата A i::= a j A k е свързано с командата (A i, a j) → A k;

· Всяко правило за заместване от формата A i::= a j е свързано с командата (A i, a j) → Z;

Пример 2.Конструирайте CA за граматиката от пример 1. Имаме A = , Където

1) V = T = (b, c)

2) Q = N U (Z) = (I, R, Z)

3) q 0 = (S) = (I)

5) δ: а) под формата на набор от команди:

б) под формата на диаграма на състоянието

Има детерминирани и недетерминирани крайни автомати. Космическият кораб се нарича недетерминиран KA (NKA), ако в неговата диаграма на състоянието няколко дъги с еднакви маркировки излизат от един връх. Например, KA от пример 2 е NKA.

За практически цели е необходимо крайният разпознавач сам да определи момента на края на входната последователност от символи и да издаде съобщение за коректността или грешката на входната последователност. За тези цели входната верига се счита за ограничена отдясно от крайния маркер ├ и интерпретираните състояния се въвеждат в диаграмата на състоянието на космическия кораб:

Z – „разрешаване на входна верига“;

O – „запомнена е грешка във входната верига“;

E – „отхвърляне на входната верига.“

Състоянията Z и E са окончателни и космическият кораб отива към тях, когато чете крайния маркер ├, съответно, след обработка на правилна или грешна входна верига. Състояние O е междинно, космическият кораб преминава в него от всяко валидно състояние на космическия кораб, когато се открие грешка във входната верига и остава там, докато пристигне крайният маркер ├, след което преминава в състояние E - „отхвърляне на входната верига. ”

Нека L 1 и L 2 са езици в азбуката

Тогава, т.е. конкатенация на езикасе състои от конкатенации на всички думи от първия език с всички думи от втория език. По-специално, ако , тогава , и ако , тогава .

Нека въведем обозначение за „степените“ на езика L:

Така L i включва всички думи, които могат да бъдат разделени на i последователни думи от L .

Итерация (L) * на езика L се формира от всички думи, които могат да бъдат разделени на няколко последователни думи от L:

Може да се представи с помощта на степени:

Често е удобно да се разглежда "скъсена" итерация на езика, която не съдържа празната дума, ако тя не съществува в езика: . Това не е нова операция, а просто удобна стенограма за израза.

Имайте предвид също, че ако разглеждаме азбуката като краен език, състоящ се от еднобуквени думи, тогава въведената по-рано нотация за набора от всички думи, включително празни думи, в азбуката съответства на определението за итерация на този език.

Следващата таблица предоставя формална индуктивна дефиниция регулярни изразивърху азбуката и езиците, които представляват.

Израз r	Език L r
	L a =(a)
Нека r 1 и r 2 са	L r1 и L r2 -представими
регулярни изрази.	тях езици.
Тогава следните изрази
са редовни	и представляват езиците:
r=(r 1 +r 2)
r=(r 1 circr 2)
r=(r 1) *	L r =L r1 *

При запис регулярни изразиЩе пропуснем знака за конкатенация и ще приемем, че операцията * има по-висок приоритет от конкатенацията и +, а конкатенацията има по-висок приоритет от +. Това ще позволи пропускането на много скоби. Например, може да се запише като 10(1 * + 0) .

Определение 5.1. две регулярни изрази r и p се наричат ​​еквивалентни, ако езиците, които представляват, са еднакви, т.е. L r = L p . В този случай пишем r = p.

Лесно е да проверите например следното свойства на редоперации:

• r + p= p+ r (комутативност на обединението),
• (r+p) +q = r + (p+q) (асоциативност на съюза),
• (r p) q = r (p q) (асоциативност на конкатенацията),
• (r *) * = r * (итерационна идемпотентност),
• (r +p) q = rq + pq(дистрибутивност).

Пример 5.1. Нека докажем, като пример, едно не толкова очевидно равенство: (r + p) * = (r * p *) *.

Нека L 1 е езикът, представен от лявата му страна, а L 2 от дясната му страна. Празната дума принадлежи и на двата езика. Ако думата не е празна, тогава чрез дефиницията на итерация тя може да бъде представена като конкатенация на поддуми, принадлежащи на езика. Но този език е подмножество на езика L"=L r * L p * (защо?). Следователно . Обратно, ако една дума , тогава тя може да бъде представена като конкатенация на поддуми, принадлежащи на езика L ". Всяка от тези поддуми v е представима във формата v= v 1 1 ... v k 1 v 1 2 ... v l 2, където за всички i=1, ... , k е поддума и за всички j=1, ... , l е поддума (възможно е k или l да е равно на 0). Но това означава, че w е конкатенация на поддуми, всяка от които принадлежи на и, следователно, .

Редовен език

В теорията на езика редовен комплект(или, на нормален език) се нарича формален език, който отговаря на следните свойства. Тези прости свойства са такива, че класът на правилните множества е удобен за изучаване като цяло и получените резултати са приложими в много важни случаи на формални езици. Тоест концепцията за редовно множество е пример за математическа структура.

Дефиниция на редовно множество

Нека Σ е крайна азбука. Редовен комплект R(Σ) в азбуката Σ се определя от следните рекурсивни свойства:

Вижте също

• Изграждане на анализатор, базиран на подхода на автоматите

Фондация Уикимедия. 2010 г.

Вижте какво е „обикновен език“ в други речници:

нормален език- - Телекомуникационни теми, основни понятия EN нормален език... Ръководство за технически преводач

- (лат. regularius, от regula правило). Правилно, правилно подредено, направено. Редовна работа на машината. Дори инсулт. Редовен живот. Коректен, достоен, монотонен живот. Речник на чуждите думи, включени в руския език.... ... Речник на чуждите думи на руския език

См … Речник на синонимите

Древна писменост- Език с дълги писмени традиции, тоест той е получил писменост, адаптирана към структурата на даден език преди няколко века, като функционирането на писмената версия на езика не е епизодично, а редовно, с... . .. Речник на социолингвистичните термини

Този термин има и други значения, вижте кечуа. Самоназвание на кечуа: Държави Qhichwa Simi, Runa Simi ... Wikipedia

Рамката на сграда с растер от колони или стълбове, базирани на стъпало с еднакъв размер (бълг.; бълг.) равномерен скелет (чех.; Čeština) pravidelný skelet (нем.; нем.) regelmäßiges Skelett (унгарски; унгарски) szabályos... ... Строителен речник

- [ФРЕНСКИ ПАРК] парк, който има геометрично правилно оформление, обикновено осово оформление (бълг.; бълг.) frenski park (чех.; Čeština) francouzský park (нем.; нем.) regelmäßiger Park; Френцошишер парк…… Строителен речник

Кечуа Самоназвание: Qhichwa Simi, Runa Simi Държави: Аржентина, Боливия, Колумбия, Перу, Чили, Еквадор Региони: Андите Официален статут: Перу ... Wikipedia

Тагалог език- (тагал, тагала, тагало; тагалог) един от филипинските езици. Районът на първоначалното разпространение е в най-важния политически, икономически и културно район на Република Филипини - централната и южната част на острова... ... Лингвистичен енциклопедичен речник

Книги

• Производни глаголи. Тайните на финландската граматика. Учебник, Сафронов V.D.. Ръководството е посветено на един от най-интересните и недостатъчно представени раздели на финландската граматика в рускоезичната учебна литература - производни глаголи. Образуват се от глаголи и от имена...