Регулярные языки и грамматики

АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ

Кафедра ТК

Тема: Регулярные языки и грамматики

относятся два эквивалентных класса грамматик:
леволинейные грамматики G(VT,VN,P,S), V=VN∪VT

А→Вγ или А→γ, где A,B∈VN, γ∈VT*

предложения языка строятся слева направо

А→γВ или А→γ, где A,B∈VN, γ∈VT*

предложения языка строятся справа налево

В классе регулярных грамматик выделяют отдельный класс –
автоматные грамматики:

леволинейные автоматные грамматики G(VT,VN,P,S), V=VN∪VT

праволинейные автоматные грамматики G(VT,VN,P,S), V=VN∪VT

А→tВ или А→t, где A,B∈VN, t∈VT

А→Вt или А→t, где A,B∈VN, t∈VT

автоматному виду

Р'

для правила 15: B→B); во множество VN'=VN'∪{B3}, в множество Р'
добавляются правила: B→B3;, B3→B)

правила 1, 5, 6, 7, 8, 10, 11, 12, 13, 14 переносятся во множество правил
Р' без изменений;

для правила 4: A→[]; во множество VN'=VN'∪{A1, A2}, в множество Р'
добавляются правила: A→A2;, A2→A1], A1→[

для правила 9: B→[a] во множество VN'=VN'∪{B1, B2}, в множество Р'
добавляются правила: B→B2], B2→B1a, B1→[

для правила 2: S→A() во множество VN'=VN'∪{S1}, в множество Р'
добавляются правила: S→ S1), S1→A(

Системное программное обеспечение

Регулярные языки и грамматики

G({"а", "[", "]", "(", ")",";"}, {S, A, B}, Р, S)
Р:
S→S;1|A()2|Ba)3
A→[];4|A(5|A)6|Aa7|A;8
B→[a]9| B]10|B)11|B(12|Ba13|B[14|B);15

Согласно алгоритму:

строится множество VT'={"а", "[", "]", "(", ")",";"};

строится множество VN'={S,A,B};

просматривается множество правил Р грамматики G:

Пример: дана регулярная леволинейная грамматика G, необходимо преобразовать ее к автоматному виду.

правил вида А→В или А→λ, во множестве правил Р' не содержится;

целевым символом грамматики G' становится символ S.

автоматная грамматика:

G'({"а", "[", "]", "(", ")",";"},