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

крім е (ε).
Припустимо, що ми маємо слово ω, тоді послідовність , а .

Формальне означення ланцюжка:
1)    ε –ланцюжок в V.
2)    Якщо – ω ланцюжок в алфавіті V і a є V, то – ωa ланцюжок в V.
3) α– ланцюжок в алфавіті V, якщо він ланцюжок внаслідок 1) або 2).

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

Приклад 1. <оператор присвоювання> ::= <ім'я> ':=' <вираз>
<вираз> ::= <первинне> | <первинне> '+' <первинне> | <первинне> '-' <первинне>
<первинне> ::= <стала> | <ім'я>
<стала> ::= '1' | '2'
<ім'я> ::= 'x' | 'y' | 'z'

"}" нази-ваються розширеними, а БНФ – розширеними БНФ, або РБНФ.

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

{X} позначає всі послідовності (у тому числі порожню) виразів, вивідних із X.

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

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

такої множини:
( T ∪ N )* N ( T ∪ N )* × ( T ∪ N )*
Якщо (ν,ω) належить множині P, то серед правил граматики G існує правило вигляду ν→ ω.
Приклад:

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

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

множині (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)

усіх – мовою, що задається (породжується) граматикою 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 → BC⇒ aC⇒ a1

називається термінальним ланцюжком, що породжується граматикою , а мова, що породжується граматикою – це множина всіх термінальних ланцюжків, що породжуються граматикою.
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 → ε | 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 }

B, C, D, E, S – нетермінали.
E, S – початкові нетермінали.
3.     U, V, …, Z – або термінал, або нетермінал.
4.     α, β – ланцюжки, що містять термінали і нетермінали.
5.     u, v, …,z – ланцюжки, що містять тільки термінали.

,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

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

B,С,S},{ a, b, c} ,P,S)
S→aSBC | abC
CB→BC
bB→bb
bC→bc
cC→cc

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

P:

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:

6) Aa→aA
7) Ab→bA
8) Ba→aB
9) Bb→bB
10) C→e
11) D→e

регулярною (автоматною), якщо
кожне правило із 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

пар Ai → ri, де Ai — різні символи нетермінального алфавіту N; ri — регулярні вирази в алфавіті N∪Т. Нетермінал першої пари вважається головним (початковим).

Приклади розширених граматик:
⮚      G10={S→АВ, В →x|y, А →z|ω};
⮚      G11={S→ (z|ω)(x|y)}. G10  G11

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

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

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