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

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

1. Означення формальних мов. Ланцюжки
1.1 Приклади мов
1.2 Задача належності. Способи визначення мов
1.3. Регулярні операції над мовами
2.Метамова БНФ
3. Розширені БНФ
4. Граматики Хомського. Основні поняття.
5. Класифікація граматик Хомського. Приклади.
6. Розпізнавачі

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

• Позначимо V V * \ e
– множину всіх слів, крім
е ( ).
• Припустимо, що ми маємо
слово , тоді
,
послідовність
а 0 .
n
n
Формальне означення ланцюжка:
1) –ланцюжок в V.
2)
Якщо – ланцюжок в алфавіті V і a є V, то – a ланцюжок в V.
3) – ланцюжок в алфавіті V, якщо він ланцюжок внаслідок 1) або 2).

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

1. Множина всіх слів в алфавітіV1 a ,
L1 , a , aa, aaa,... a n n 0
2. Нехай V2 a, b,1 , L2 визначає множину ідентифікаторів:
L2 a , b, a1, b1, aa , ab, aa1,... .
3. V3 a, b, c , L3 a n bc n n 0 , aabcc L3 , abcc L3 .
k
V
{
a
}
L
V
|
|
2
, k 0,1,2,... ,aa L4 , aaaa L4 ,aaa L4 .
4
4. 4
, 4
5.
V5 = {a, b, c}; L5 = {anbcm | n, m 0}, aaaabcc L5, cbaa L5.
6.
V6 = {a, b, c}; L6= {x | у ланцюжку х кількості входжень a, b і c рівні},
cbaba L6, ccb L6.

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

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

Нехай є три мови:
L1, L2 , L
з алфавітуV .
Об’єднання L1 L2 буде визначати нову мову:
L 1 L 2 L 1 або L 2
Приклад: a , ab
, ba
a , ba
, bb
a , ab
, ba , bb
.
Конкатенацією (катенацією) мовL1 і L2 називається
L1 L 2 1 2 1 L1 , 2 L 2
Приклад: a , b c , d , e ac , ad , a , bc , bd , b .
0
i
i 1
L
L
Піднесення до степеня мови . e . L L L .
e, a, aa 2 e, a, aa e, a, aa e, a, aa , aaa , aaaa
Приклад:
.
Ітерація мови:
L* i L , i 0
e
L L2 Ln
.

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

<поняття> має структуру <метавираз>
<поняття> ::= <метавираз>
БНФ оператора присвоєння:
<оператор присвоювання> ::= <ім'я> ':=' <вираз>
<ім'я>::=<буква><послідовність букв і цифр >
Приклад 1. <оператор присвоювання> ::= <ім'я> ':=' <вираз>
<вираз> ::= <первинне> | <первинне> '+' <первинне> |
<первинне> '-' <первинне>
<первинне> ::= <стала> | <ім'я>
<стала> ::= '1' | '2'
<ім'я> ::= 'x' | 'y' | 'z'

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

Означення: Метавирази з символами "(", ")", "[", "]", "{", "}" називаються розширеними, а БНФ – розширеними БНФ, або РБНФ.
X, Y, Z, … , T – довільні метавирази (можливо, порожні),
N – нетермінал
N ::= X Z Y
…
N ::= X T Y
<вираз> ::=
<первинне> '+' <первинне> |
<первинне> '-' <первинне>
N ::= X ( Z | … | T ) Y
<вираз> ::=
<первинне> ('+' | '-') <первинне>

8.

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

9. Ітераційні дужки “{“ , “}”

Якщо X – довільний метавираз, то метавираз {X} позначає всі
послідовності (у тому числі порожню) виразів, вивідних із X.
Прикляд 2. Визначимо записати поняття
«ідентифікатор» в алфавіті V={A,B,C,0,1}
<Ід> ::=<Б> { <Б> | <Ц> }
<Б> ::= 'A' | 'B' | 'C'
<Ц> ::= '0' | '1'
<Ід> ::=
( 'A' | 'B' | 'C' ){ 'A' | 'B' | 'C' | '0' | '1' }

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

<expression> ::= <assignment-expression>
| <expression> , <assignment-expression>
<assignment-operator> ::= =
| *=
| /=
| %=
| +=
| -=
| <<=
| >>=
| &=
| ^=
| |=

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

<selection-statement> ::= if ( <expression> ) <statement>
| if ( <expression> ) <statement> else <statement>
| switch ( <expression> ) <statement>
<iteration-statement> ::= while ( <expression> ) <statement>
| do <statement> while ( <expression> ) ;
| for ( {<expression>}; {<expression>} ;
{<expression>} ) <statement>
Тут круглі дужки - термінальні символи, а не метасимволи

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

Означення: Граматикою Хомського називається четвірка
G = (N, T, P, S),
N – множина позначень понять мови, тобто нетермінальних
символів (нетерміналів).
T – алфавіт означуваної мови, або множина термінальних
символів (терміналів).
T N =ø
P – множина правил виведення (продукцій) вигляду v w, де
v ( T N )* N ( T N )* , w ( T N )*
тобто правий ланцюжок є довільною послідовністю терміналів
і нетерміналів, а лівий містить принаймні один нетермінал.
S – початковий нетермінал із множини N, або позначення
головного поняття, яким позначаються слова мови.

13. How a grammar generates sentences

G = (N, T, P, S),
Example: consider the grammar:
P:
S NP VP NP
NP John
NP a book
VP reads
Terminals T: ‘John’, ‘a book’, ‘reads’. Nonterminals N: S, NP, VP.
We start with S.
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
13
the language described by the grammar.

14. How a grammar generates sentences

• Summary of the derivation:
S => NP VP NP
John VP NP
John reads NP
John reads a book
Another derivation:
S => NP VP NP
a book VP NP
a book reads NP
a book reads John
Another derivation:
S => NP VP NP
John VP NP
John reads NP
John reads John
14

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

Можна вважати P – скінченною підмножиною такої множини:
( T N )* N ( T N )* ( T N )*
Якщо ( , ) належить множині P, то серед правил граматики G
існує правило вигляду .
Приклад: AB, CDE P
Якщо
AB CDE
xyABLC , G , то xyCDELC 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

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

Приклад . 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 }

17. Визначимо ряд понять:

1. На множині слів об'єднаного алфавіту (T N)* означається
відношення безпосередньої виводимості, позначене знаком
G (або , коли відомо, якою саме є G):
v G w, якщо v = x1 u x2 ,
w = x1 y x2 ,
u y P.
При цьому кажуть, що w безпосередньо виводиться з v
застосуванням продукції u y.
Приклад . 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

18.

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.
Приклад . 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)
3. Якщо S G*w, то послідовність S … w називається
виведенням слова w у граматиці G, а слово w – вивідним.
Приклад .Слова A, BC, aC, a1 вивідні в граматиці G1.

19.

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 }
S 0 A1 00 A11 0011
Приклад . 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 BC aC a1

20.

5. Вивідний ланцюжок граматики , що не містить
нетермінальних символів називається термінальним
ланцюжком, що породжується граматикою , а мова, що
породжується граматикою – це множина всіх термінальних
ланцюжків, що породжуються граматикою.
6. Граматики називаються еквівалентними, якщо задають
ту саму мову.
Приклад . 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 }
Приклад . 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 | C(a| …|z|0|…|9)}, I )

21. Введемо позначення:

1.
Будемо позначати a,b, …,0,1, …9 – термінали.
2.
A, B, C, D, E, S – нетермінали.
E, S – початкові нетермінали.
3.
U, V, …, Z – або термінал, або нетермінал.
4.
, – ланцюжки, що містять термінали і нетермінали.
5.
u, v, …,z – ланцюжки, що містять тільки термінали.

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

Граматики можна класифікувати за виглядом їх правил.
Класифікація нижче називається ієрархією за Хомським.
Нехай G ( N , T , P, S ).
Означення 1. Граматика G називається праволінійною
(ліволінійною), якщо
*
A
,
B
N
,
x
T
A x, A xB , де
*
A
,
B
N
,
x
T
(якщо A x, A Bx , де
).
Приклад. G 3 ({S }, {0,1}, {S 0 S | 1S | e}, S ).

23.

Означення 2. Граматика G називається контекстно-вільною
(безконтекстною), якщо кожне правило з P має вигляд:
A , A N , (T N ) * .
Застосування продукції A w до ланцюжка uAv не
залежить, тобто є вільним від сусідніх з A символів,
які утворюють контекст uv.
Приклад контекстно-вільної граматики:
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

24.

Означення 3. Граматика G називається контекстнозалежною або нескоротною, якщо кожне правило з P
має вигляд:
, , (T N )* , | | | |.
Контекстно-залежні граматики не допускають правила
вигляду A e.
Приклад контекстно-залежної граматики:
G5 = ({ B,С,S},{ a, b, c} ,P,S)
P: • S aSBC | abC
• CB BC
• bB bb
• bC bc
L (G5 ) {a n b n c n | n 1}.
• cC cc
S=>aSBC=>aabCBC=> aabBCC=> aabbCC => aabbcC
=> aabbcc

25.

Означення 4. Граматика, яка не підлягає жодним обмеженням
з означень 1,2,3 називається необмеженою або граматикою
загального вигляду.
Приклад необмеженої граматики:
G6 = ({ A,B,С,D,S},{ a, b} ,P,S)
P: 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
S (1) CD ( 2 ) aCAD ( 3) abCBAD ( 4 ) abCBaD (8) abCaBD (5)
(5) abCabD (10),(11) abab.
L(G6 ) ( | {a, b}* ).

26.

L(G6 ) ( | {a, b}* ).
L(G6 ) ( | {a, b}* ).
L(G6 ) ( | {a, b}* ).
S CD
1) S CD
Для n 1 : C ( 2 ) ( 3),n c1c2 ..cnCX n X n 1.. X 1
2) C aCA
(10 )
c1c2 ..cn X n X n 1.. X 1.
3) C bCB
ci a тоді і тільки тоді, коли X i A.
4) AD aD
ci b тоді і тільки тоді, коли X i B.
5) BD bD
6) Aa aA
X n X n 1.. X 1D ( 4 ) ( 5) X n X n 1.. X 2c1D
7) Ab bA
( 6 ) ( 9 ),n 1
c1 X n X n 1.. X 2 D
8) Ba aB
* c1c2 X n X n 1.. X 3 D
9) Bb bB
10) C e
*( 4 ) ( 9 ) c1c2 ..cn D (11) c1c2 ..cn .
11) D e
*
S c1c 2 ..c n c1c 2 ..c n

27.

Означення 5. Праволінійна граматика G = (Т, N, 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

28.

Означення 6. Граматика G називається розширеною
граматикою, якщо вона задається списком пар Ai
ri, де Ai — різні символи нетермінального алфавіту
N; ri — регулярні вирази в алфавіті N Т.
Нетермінал першої пари вважається головним
(початковим).
Приклади розширених граматик:
G10={S АВ, В x|y, А z| };
G11={S (z| )(x|y)}.
G10 G11

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

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

Розпізнавач – це схематизований алгоритм, який визначає
деяку множину ланцюжків.
Розпізнавач
складається
з трьох частин:
вхідна стрічка;
керуючий пристрій із
скінченню пам’яттю;
• робоча
(допоміжна)
пам’ять.

31.

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

32.

Для кожного класу граматик із ієрархії Хомського існує свій
клас розпізнавачів, які визначають ті самі класи мов, що і
граматики, наприклад:
1)
Мова L праволінійна тоді і тільки тоді,
коли вона розпізнається одностороннім
детермніованим скінченним розпізнавачем.
2)
Мова L контекстно-вільна тоді і тільки
тоді, коли вона визначається одностороннім
недетермніованим розпізнавачем з магазинною
пам’яттю.
3) Мова L контекстно-залежна тоді і тільки
тоді, коли вона розпізнається двостороннім
недетермніованим обмеженим розпізнавачем.
Тема 4