Задача належності. Способи визначення мов Регулярні операції над мовами

Ім'я файлу: Tema_2._Elementi_teor_formalnikh (2).pptx
Розширення: pptx
Розмір: 874кб.
Дата: 16.03.2024
скачати

Тема 2. Елементи теорії формальних мов

1. Означення формальних мов. Ланцюжки

1.1 Приклади мов

1.2 Задача належності. Способи визначення мов

1.3. Регулярні операції над мовами

2.Метамова БНФ

3. Розширені БНФ

4. Граматики Хомського. Основні поняття.

5. Класифікація граматик Хомського. Приклади.

6. Розпізнавачі (самостійно опрацювати)

1. Означення формальних мов. Ланцюжки

Алфавітом V називається скінченна множина символів.
Словом (фразою, або ланцюжком) у алфавіті V називається послідовність символів із V. Порожнє слово – це послідовність довжиною 0, позначена буквою  або е.

Позначимо – множину всіх слів, крім е ().

Довільна підмножина множини V* називається формальною мовою

Лексика, синтаксис і семантика штучних мов

Основою кожної мови є алфавіт. Штучна мова містить у собі правила утворення найпростіших виразів мови (лексем) і правила побудови складніших виразів із більш простих. Ці дві групи правил називаються відповідно лексичною та синтаксичною системами мови. Правила, за якими виразам мови зіставляється зміст, утворюють семантичну систему мови. Для опису лексики, синтаксису і семантики використовуються різні засоби. Так, опис лексем мови може бути виконаний, наприклад, за допомогою праволінійних граматик, регулярних виразів або скінченних автоматів, опис синтаксису мови – із застосуванням контекстно-вільних граматик з певними обмеженнями або магазинних автоматів, а опис її семантики – за допомогою атрибутних граматик.

Формальне означення ланцюжка

1)  –ланцюжок в V.

2) Якщо –  ланцюжок в алфавіті V і a ∈ V, то – a ланцюжок в V.

3) – ланцюжок в алфавіті V, якщо він ланцюжок внаслідок 1) або 2).

Якщо x і y – деякі ланцюжки, то xy називається зчепленням або конкатенацією двох ланцюжків. Наприклад, якщо x=ab, а y=cd, a∈V , b∈V , c∈V, d∈V, вірні рівності xy=abcd, x = x = x . Нехай x, y, z – деякі ланцюжки. Тоді для ланцюжка xyz, x – називається префіксом, z – суфіксом, y – підланцюжком ланцюжка xyz. Довжина ланцюжка дорівнює кількості символів в ланцюжку, позначається через знак модуля. Отже, якщо x=ab, де a та b символи з алфавіту V, то довжина ланцюжка | x| = 2 . Довжина порожнього слова дорівнює нулю (|  |=0).

1.1. Приклади формальних мов

c

1.2. Задача належності. Способи визначення мов

Довільний скінчений механізм завдання мови називається граматикою

Задача перевірки, чи належить слово w мові L, називається задачею належності, або проблемою слів.

1.3. Регулярні операції над мовами

2. Метамова БНФ

Будемо позначати поняття мови кутовими дужками (наприклад <ідентифікатор>) і називати поняття нетермінальними символами.

Символи і лексеми мови будемо брати в апострофи і називати термінальними символами або терміналами. Послідовність, яка складена з терміналів і нетерміналів, називається метавиразом.

Синтаксичні правила, записані у вигляді

<поняття> ::= <метавираз>, називаються формами Бекуса-Наура (БНФ).

Поняття, записане в БНФ ліворуч від "::=", називається її лівою частиною, а метавираз праворуч – правою. Знак "::=" не є символом мови й називається метасимволом.

БНФ – це вираз у алфавіті, що складається з терміналів, нетерміналів і спеціальних метасимволів.

Приклади БНФ

<поняття> має структуру <метавираз>

<поняття> ::= <метавираз>

БНФ оператора присвоєння:

<оператор присвоювання> ::= <ім'я> ‘:=' <вираз>

<ім'я>::=<буква><послідовність букв і цифр >

…

Приклад. <оператор присвоювання> ::= <ім'я> ':=' <вираз>

<вираз> ::= <первинне> | <первинне> '+' <первинне> | <первинне> '-' <первинне>

<первинне> ::= <стала> | <ім'я>

<стала> ::= '1' | '2'

<ім'я> ::= 'x' | 'y' | 'z'

Сукупність BNF

Рекурсивні БНФ: ціле число та ідентифікатор

<integer> ::= <digit> | <integer><digit>

<identifier> ::= <letter> | <identifier><letter> | <identifier><digit>

<digit> ::= '0' | '1' | '2'| '3' | '4'| '5' | '6'| '7' | '8'| '9'

<letter> ::= 'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G' | 'H' | 'I' | 'J' | 'K' | 'L' | 'M' | 'N' | 'O' | 'P' | 'Q' | 'R' | 'S' | 'T' | 'U' | 'V' | 'W' | 'X' | 'Y' | 'Z' | 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h' | 'i' | 'j' | 'k' | 'l' | 'm' | 'n' | 'o' | 'p' | 'q' | 'r' | 's' | 't' | 'u' | 'v' | 'w' | 'x' | 'y' | 'z'

Сукупність BNF: Дійсне число

<real-number> ::= <integer-part> '.' <fraction>

<integer-part> ::= <empty>

<integer-part> ::= <digit-sequence>

<fraction> ::= <digit-sequence>

<digit-sequence> ::= <digit> | <digit> <digit-sequence>

<digit> ::= '0' | '1' | '2'| '3' | '4'| '5' | '6'| '7' | '8'| '9'

<empty> ::= 

3. Розширені БНФ

Означення: Метавирази з символами '(', ')', '[', ']', '{', '}' називаються розширеними, а БНФ – розширеними БНФ, або РБНФ.

X, Y, Z, … , T – довільні метавирази (можливо, порожні), N – нетермінал

N ::= X Z Y … N ::= X T Y	N ::= X ( Z \| … \| T ) Y
<вираз> ::= <первинне> '+' <первинне> \| <первинне> '-' <первинне>	<вираз> ::= <первинне> ('+' \| '-') <первинне>

N ::= X Z Y N ::= X Y	N ::= X [ Z ] Y
<вираз> ::= <первинне> \| <первинне> ('+'\| '-') <первинне>	<вираз> ::= <первинне> [ ('+'\| '-') <первинне> ]
<оператор присвоювання> ::= <ім'я> ':=' <вираз> <вираз> ::= <первинне> \| <первинне> '+' <первинне> \| <первинне> '-' <первинне> <первинне> ::= <стала> \| <ім'я> <стала> ::= '1' \| '2' <ім'я> ::= 'x' \| 'y' \| 'z'	<оператор присвоювання> ::= <ім'я> ':=' ('1' \| '2' \| <ім'я>) [ ('+'\| '-') ('1' \| '2' \| <ім'я>) ] <ім'я> ::= 'x' \| 'y' \| 'z'

Ітераційні дужки '{' , '}'

Якщо X – довільний метавираз, то метавираз {X} позначає всі послідовності (у тому числі порожню) виразів, вивідних із X.

Прикляд. Визначимо записати поняття «ідентифікатор» в алфавіті V={A,B,C,0,1}

<Ід> ::= <Б> { <Б> | <Ц> }

<Б> ::= 'A' | 'B' | 'C'

<Ц> ::= '0' | '1'

<Ід> ::=

( 'A' | 'B' | 'C' ){ 'A' | 'B' | 'C' | '0' | '1' }

BNF <Ід> ::= <Б> | <Ід> <Б> | <Ід> <Ц>

EBNF

Перетворення рекурсивної BNF для оператора присвоєння у EBNF без прямої рекурсії

V={A,B,C,+,*,(,),:=}

B := C * (A * C + B)

A := A * (B + (C * A))

BNF ::= ':='

::= '+'

                  | '*'

                  |   '(' ')'

                  |

       EBNF    ::= ':='

             ::= {('+' | '*') }

             ::= '(' ')'

The syntax of C in Backus-Naur Form (fragment 1)

::=

| ,

::= =

| *=

| /=

| %=

| +=

| -=

| <<=

| >>=

| &=

| ^=

| |=

::= if ( )

| if ( ) else

| switch ( )

::= while ( )

| do while ( ) ;

| for ( {}? ; {}? ; {}? )

https://cs.wmich.edu/gupta/teaching/cs4850/sumII06/The%20syntax%20of%20C%20in%20Backus-Naur%20form.htm

The syntax of C in Backus-Naur Form (fragment 2)

::= if ( )

| if ( ) else

| switch ( )

::= while ( )

| do while ( ) ;

| for ( {}; {} ; {} )

Тут круглі дужки, “;” і ключові слова - термінальні символи

Розширені БНФ (EBNF) для слів, які відповідають масці

Метасимвол – :

Зміст метасимволу – непорожній ланцюжок бінарних цифр.

Маска: ab:f::

Слова, які відповідають масці: ab1100f01 ab000f00 ab1f011

EBNF для слів:

::= 'ab''f'

::= (0|1){0|1}

Лабораторна робота 1а:

написати EBNF для довільної маски з вашими метасимволами;
написати програму, яка генерує задану кількість випадкових слів по введеній масці та виводить їх на консоль і у файл (будь-яка мова програмування).

4. Граматики Хомського. Основні поняття

Означення: Граматикою Хомського називається четвірка

G = (N, T, P, S),

N – множина позначень понять мови, тобто нетермінальних символів (нетерміналів).

T – алфавіт означуваної мови, або множина термінальних символів (терміналів). T ⋂ N =ø

P – множина правил виведення (продукцій) вигляду v® w, де

v Î ( T È N )* N ( T È N )* , w Î ( T È N )*

тобто правий ланцюжок є довільною послідовністю терміналів і нетерміналів, а лівий містить принаймні один нетермінал.

S – початковий нетермінал із множини N, або позначення головного поняття, яким позначаються слова мови.

Як граматика генерує речення

We apply the first rule to replace S with NP VP NP:

S => NP VP NP

John VP NP
John reads NP
John reads a book

At this point, the string consists only of terminals and we must stop. It is a valid sentence belonging to the language described by the grammar.

Terminals T={John, a book, reads},

Nonterminals N={S, NP, VP},

We start with S.

G = (N, T, P, S),

P:

S ® NP VP NP

NP ® John

NP ® a book

VP ® reads

G = (N, T, P, S),

T={John, a book, reads}

N={S, NP, VP},

P: S ® NP VP NP

NP ® John

NP ® a book

VP ® reads

Another derivation:

2) S => NP VP NP

a book VP NP
a book reads NP
a book reads John

Another derivation:

John VP NP
John reads NP
John reads John

Another derivation:

a book VP NP
a book reads NP
a book reads a book

Summary of the derivation:

1) S => NP VP NP

John VP NP
John reads NP
John reads a book

S - речення

NP- iменник, VP-дієслово

G = (N, T, P, S)

T={заняття, викладач, проводить}

N={S, N, V},

P: S ® N V N

N ® заняття

N ® викладач

V ® проводить

2) S => N V N

викладач V N
викладач проводить N
викладач проводить заняття

два виведення з чотирьох можливих:

1) S => N V N

заняття V N
заняття проводить N
заняття проводить викладач

BNF

::=

::= ‘заняття’ | ‘викладач’

::= ‘проводить’

S - речення

N- iменник, V- дієслово
G = (N, T, P, S), N={S,A,B,C}, T={a,b,c}

P:

S ® ABC

A ® aA | a

B ® bB | b

C ® cC | c

Граматика описує слова, які починаються з 1 або більшої кількості символів а, далі слідують 1 або більше символів b, далі - 1 або більше символів c. Нескінченна кількість виведень.

SÞ ABC Þ aABCÞ aaABC Þ aaaBCÞ aaabCÞ aaabcCÞ aaabcc

Можна вважати P – скінченною підмножиною такої множини:

( T È N )* N ( T È N )*  ( T È N )*

Якщо (,) належить множині P, то серед правил граматики G існує правило вигляду  .

Приклад:

v® w1 і v® w2

v® w1ww2 і v® w1w2

v® w1u1w2 і v® w1u2w2

v® w1 | w2

v® w1[w]w2

v1® w1(u1|u2)w2

Приклади граматик Хомського

Приклад . G0 =(N, T, P, S)

N: { A, S }

T: {0,1}

P: S ® 0A1, 0A ® 00A1, A ® e

Приклад . G1 =({ A, B, C, D },{ a, 1, 2 },

{ A ® BC, A ® BD, A ® B, B ® a, C ® 1, D ® 2 }, A )

P можна переписати у вигляді

{ A ® B [ C | D ], B ® a, C ® 1, D ® 2 }
Визначимо ряд понять:

Приклад . G1 =({ A, B, C, D },{ a, 1, 2 },

{ A ® BC, A ® BD, A ® B, B ® a, C ® 1, D ® 2 }, A )

BCÞ aC застосуванням продукції B® a,

aCÞ a1 застосуванням C® 1

1. На множині слів об'єднаного алфавіту (TÈ N)* означається відношення безпосередньої виводимості, позначене знаком Þ G (або Þ , коли відомо, якою саме є G):

v Þ G w, якщо v = x1 u x2 , w = x1 y x2 , u ® y Î P.

При цьому кажуть, що w безпосередньо виводиться з v застосуванням продукції u® y.

Приклад .Слова A, BC, aC, a1 вивідні в граматиці G1.

2. На множині (TÈN)* означається відношення виводимості, позначене Þ*G (або Þ*, коли відомо, якою саме є G): v Þ* w, якщо v=w або існує послідовність w1, w2, …, wn слів, де n³ 1, така, що vÞ w1, w1Þ w2, … , wn-1Þ wn, wn=w. Послідовність vÞw1Þw2Þ…Þwn називається виведенням wn із v, а n – довжиною виведення.

v Þ* w можна уточнити v Þn w.

3. Якщо SÞ G*w, то послідовність SÞ …Þ w називається виведенням слова w у граматиці G, а слово w – вивідним.

Приклад . G1 =({ A, B, C, D },{ a, 1, 2 },

{ A ® BC, A ® BD, A ® B, B ® a, C ® 1, D ® 2 }, A )

BCÞ* a1, оскільки BCÞ aC, aCÞ a1. (BC Þ2 a1)

4. Вивідні слова в алфавіті T називаються породжуваними, а множина їх усіх – мовою, що задається (породжується) граматикою G:

L(G) = {w | wÎ T* та S Þ * w }.

Приклад . G0 =(N, T, P, S)

P: S ® 0A1, 0A ® 00A1, A ® e

N: { A, S }

T: {0,1}

L(G0) = {0n1n | n≥1 }

Приклад . G1 =({ A, B, C, D },{ a, 1, 2 },

{ A ® BC, A ® BD, A ® B, B ® a, C ® 1, D ® 2 }, A )

L(G1) = {a, a 1, a 2 }

A Þ BÞ a

A Þ BCÞ aCÞ a1

A Þ BDÞ aDÞ a2

5. Вивідний ланцюжок граматики , що не містить нетермінальних символів називається термінальним ланцюжком, що породжується граматикою , а мова, що породжується граматикою – це множина всіх термінальних ланцюжків, що породжуються граматикою.

6. Граматики називаються еквівалентними, якщо задають ту саму мову.

Приклад . G2 = ({ I, L, D },{ a, …, z, 0, …, 9 },

{ I ® L | IL | ID, L ® a | … | z, D ® 0 | ... | 9 }, I )

G2 = ({I, C}, {a, …, z, 0, …, 9},

{I ® (a|…|z)C, C ® e | C(a| …|z|0|…|9)}, I )

Приклад . G1 =({ A, B, C, D },{ a, 1, 2 },

{ A ® BC, A ® BD, A ® B, B ® a, C ® 1, D ® 2 }, A )

G1 = ({ A }, { a, 1, 2 }, { A ® a [ 1 | 2 ] }, A ) L(G1) = {a, a 1, a 2 }
Введемо позначення:

1.     Будемо позначати a,b, …,0,1, …9 – термінали.

2.     A, B, C, D, E, S – нетермінали.

E, S – початкові нетермінали.

3.     U, V, …, Z – або термінал, або нетермінал.

4.     ,  – ланцюжки, що містять термінали і нетермінали.

5.     u, v, …,z – ланцюжки, що містять тільки термінали.
Розширені БНФ (EBNF) і граматика для слів, які відповідають масці

Метасимвол – :

Зміст метасимволу – непорожній ланцюжок бінарних цифр.

Маска:  ab:f::

Слова, які відповідають масці: ab1100f01 ab000f00 ab1f011

EBNF для слів:

::= 'ab''f'

::= (0|1){0|1}

G = (N, T, P, S),

N={W,M},

T={a,b,f,0,1},

P={W ®abMfMM, M ®0, M ®1, M ®M1, M ® M0},

S=W

5. Класифікація граматик Хомського. Приклади

Приклади (праволінійна і ліволінійна граматики)

Gleft =({ S},{ 0,1},{ S ® 0, S ®1, S ® S0, S ® S1 }, S )

Gright =({ S},{ 0,1,2},{ S ® 0S, S ®1S, S ® 2S, S ® e }, S )

Непорожній ланцюжок бінарних цифр

(двійкові числа)

Трійкові числа і порожній ланцюжок

Приклад контекстно-вільної граматики:

Застосування продукції A® w до ланцюжка uAv не залежить, тобто є вільним від сусідніх з A символів, які утворюють контекст uv.

Слова, які відповідають масці: ab1100f01 ab000f00 ab1f011

G = (N, T, P, S),

N={W,M},

T={a,b,f,0,1},

P={W ®abMfMM, M ®0, M ®1, M ®M1, M ® M0},

S=W

Метасимвол – : (непорожній ланцюжок бінарних цифр)

Маска:  ab:f::

Приклад контекстно-вільної граматики:

G4 = ({ E, T,F},{ a, *, +,(,)} ,P,E)

P: EE+T|T

TT*F|F

F(E)|a

E=>E+T=>T+T=>F+T=>a+T=>a+T*F=>a+a*F=>a+a*a

E=>E+T=>T+T=>F+T=>(E)+T=>(E+T)+T=>*((E+T)+T)+T=>

=>((T+T)+T)+T =>8 ((a+a)+a)+a

S=>aSBC=>aabCBC=> aabBCC=> aabbCC => aabbcC => aabbcc

Приклад контекстно-залежної граматики:

G5 = ({ B,С,S},{ a, b, c} ,P,S)

SaSBC | abC

CBBC

bBbb

bCbc

cCcc

Контекстно-залежні граматики не допускають правила вигляду A e.

P:

Приклад необмеженої граматики:

G0 =(N, T, P, S)

P: S ® 0A1, 0A ® 00A1, A ® e

N: { A, S }

T: {0,1}

L(G0) = {0n1n | n≥1 }

Приклад необмеженої граматики:

G6 = ({ A,B,С,D,S},{ a, b} ,P,S)

1) SCD 6) AaaA

2) CaCA 7) AbbA

3) CbCB 8) BaaB

4) ADaD 9) BbbB

5) BDbD 10) Ce

11) De

P:

1) SCD

2) CaCA

3) CbCB

4) ADaD

5) BDbD

6) AaaA

7) AbbA

8) BaaB

9) BbbB

10) Ce

11) De

Означення 5. Праволінійна граматика G = (N, T, P, S) називається регулярною (автоматною), якщо

кожне правило із P, за виключенням Se, має вигляд AaB або Aa, де A,B є N, a є T;

якщо Se належить P, то S не зустрічається в правих частинах правил.

Приклади:

G7 = ({ A,S}, { a, b}, P, S) P: SabA | e, ASaa | b

G8 = ({ A,C,S}, { a, b}, P, S) P: S aC | e , Aa, C bA | bC | e

G9 = ({S}, { 0, 1}, P, S) P: S0S | 1S | e

Означення 6. Граматика G називається розширеною граматикою, якщо вона задається списком пар Ai  ri, де

Ai — різні символи нетермінального алфавіту N;

ri — регулярні вирази в алфавіті NТ.

Нетермінал першої пари вважається головним (початковим).

Приклади розширених граматик:

Ø      G10={SАВ, В x|y, А z|};

Ø      G11={S (z|)(x|y)}.

G10 еквівалентна G11
Адреса://fpm.chnu Гіперпосилання 'Системне програмування', Вкладинка 'Програмний супровід'

5. Розпізнавачі

Розпізнавач складається

з трьох частин:

вхідна стрічка;

керуючий пристрій із скінченню пам'яттю;

робоча (допоміжна) пам'ять.

Розпізнавач – це схематизований алгоритм, який визначає деяку множину ланцюжків.

Означення 1. Керуючий пристрій називається детермінованим, якщо для кожної конфігурації існує не більше одного наступного детермінованого кроку.

Означення 2. Конфігурація називається початковою, якщо керуючий пристрій знаходиться в заданому початковому стані, вхідна голівка розглядає найлівіший символ, а пам'ять має початкове вмістиме.

Означення 3. Конфігурація називається заключною, якщо керуючий пристрій знаходиться в одному із заключних станів, а вхідна голівка оглядає правий кінець стрічки.

Означення 4. Кажуть, що розпізнавач допускає вхідний рядок, якщо починаючи із початкової кофігурації, розпізнавач може виконати послідовність кроків, що закінчиться заключною конфігурацією.

Означення 5. Мова, що дозволяється розпізнавачем – це множина вхідних ланцюжків, які він допускає.

1)     Мова L праволінійна тоді і тільки тоді, коли вона розпізнається одностороннім детермінованим скінченним розпізнавачем.

2)     Мова L контекстно-вільна тоді і тільки тоді, коли вона визначається одностороннім недетермінованим розпізнавачем з магазинною пам'яттю.

3)     Мова L контекстно-залежна тоді і тільки тоді, коли вона розпізнається двостороннім недетермінованим обмеженим розпізнавачем.

Для кожного класу граматик із ієрархії Хомського існує свій клас розпізнавачів, які визначають ті самі класи мов, що і граматики, наприклад:

Тема 4

© Усі права захищені
написати до нас