Способы описания формальных языков. Лекция 3

распознавания
языков
4 Регулярные грамматики и языки

{A, S}, P1, S), где

Р1: 1) S→ 0A1; 2) 0A→ 00A1; 3) A→ε.

G3 = ({0, 1}, {S}, P3, S), где P3: S → 0S1 | 01.

G1 ≅ G3, т.к. L(G1 ) =L( G3) = {0n1n | n>0}

где P2: S → 0S1 | ε.

G1 ≅ε G2, т.к. L( G2) = {0n1n | n≥0}

Пример

Эквивалентность грамматик

G1=({0, 1}, {A, S}, P1, S), где

Р1: 1) S→ 0A1; 2) 0A→ 00A1; 3) A→ε.

α→β, где α ∈ (VT ∪ VN)+,
β ∈ (VT ∪ VN)* и |α| ≤ |β|,

Т2. Контекстно-свободная

Р : А→β, где А ∈ VN, β ∈ V *

Т3. Регулярная, выровненная вправо(влево)

А→ ε

, S→ ε

G = (VT, VN, P, S)

P: A → aB | a, где a∈VT; A, B ∈VN
A → Ba | a

контекстно-свободная грамматика;
КЗ – контекстно-зависимая грамматика;
Т0 – фразовая грамматика.

F → AFB | AB; 4) Cb → bC;
5) AB → bBA; 6) CB → C;
7) Ab → bA; 8) bCD → ε.

CB → BC;
3) aB → ab; 4) bB → bb;
5) bC → bc; 6) cC → cc.

Q → cSc.

стоящих а}

1) S → A⊥ | B⊥;
2) A → a | Ba;
3) B → b | Bb | Ab.

регулярное множество строк.

∅;

Регулярное множество:

{ε};

{а} для некоторого а ∈Σ;

конечное число объединений,
сцеплений и итераций.

леммы о разрастании языка

(0000111, 000111, 001111, 00111111 …)

00111

Язык L2 = {0n1n | n ≥1} - нерегулярный

000111

(0000111, 0001111, 000111111 …)

( обозначает: {ε});

3) а ∈Σ ( обозначает: {а});

4) если p и q ( обозначающие P и Q), то :

а) p|q или p+q (обозначает: P∪Q) - альтернатива;

б) pq или p⋅q (обозначает: PQ = {xy | x ∈P, y ∈Q}) -конкатенация;

в) p* ( обозначает: P* ) - итерация.

из единиц,
включая пустую строку

строки, образованные из символов 0 и 1, включая пустую строку

строки, начинающиеся с нуля и последующей строки единиц, включая пустую

строки, образованные из символов 0 и 1,
включая пустую, обязательно
оканчивающиеся строкой 011

01

0|1

0|1*

(0|1)*

01*

(0|1)*011