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

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 .
4. V4 {a} , L4 V4 | | 2 k , k 0,1,2,... , aa L4 , aaaa L4 , aaa L4 .
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 L1 або L2
L1 L2
Приклад: a , ab, ba a , ba , bb a , ab, ba , bb .
Конкатенацією (катенацією) мов
L1L2 1 2 1 L1 , 2 L2
L1
і
L2
називається
Приклад: a , b c, d , e ac, ad , a , bc, bd , b .
Піднесення до степеня мови L . L0 e . Li Li 1L .
2
e
,
a
,
aa
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. 4. Граматики Хомського. Основні поняття

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

11. 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 w1 | w2
v w1ww2 і v w1w2
v w1[w]w2
v w1u1w2 і v w1u2w2
v1 w1(u1|u2)w2

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

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

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

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 застосуванням продукції
aC a1
застосуванням
C 1
B a,

14.

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.

15.

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}
S 0 A1 00 A11 0011
L(G0) = {0 1 | n 1 }
Приклад . G1 =({ A, B, C, D },{ a, 1, 2 },
n n
{ A BC, A BD, A B, B a, C 1, D 2 }, A )
A BC aC a1
L(G ) = {a, a 1, a 2 }
1

16.

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},

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

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

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

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

19.

Означення 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

20.

Означення 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
cC cc
L (G5 ) {a n b n c n | n 1}.
S=>aSBC=>aabCBC=> aabBCC=> aabbCC => aabbcC
=> aabbcc

21.

Означення 4. Граматика, яка не підлягає жодним обмеженням
з означень 1,2,3 називається необмеженою або граматикою
загального вигляду.
P:
Приклад необмеженої граматики:
G6 = ({ A,B,С,D,S},{ a, b} ,P,S)
1)
2)
3)
4)
5)
S CD
C aCA
C bCB
AD aD
BD bD
6) Aa aA
7) Ab bA
8) Ba aB
9) Bb bB
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}* ).

22.

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 * c c ..c c c ..c
1
2
n 1
2
n

23.

Означення 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

24.

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

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

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

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

27.

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

28.

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