Содержание
- 2. Системное программное обеспечение Тема № 8 Регулярные языки и грамматики
- 3. Системное программное обеспечение Регулярные языки и грамматики Автоматные регулярные грамматики К регулярным грамматикам относятся два эквивалентных
- 4. Системное программное обеспечение Регулярные языки и грамматики Схема алгоритма преобразования регулярной грамматики к автоматному виду
- 5. для правила 3: S→Ba) во множество VN'=VN'∪{S2}, в множество Р' добавляются правила: S→ S2), S2→Ba для
- 7. Скачать презентацию
Системное программное обеспечение
Тема № 8
Регулярные языки и грамматики
Системное программное обеспечение
Тема № 8
Регулярные языки и грамматики
Системное программное обеспечение
Регулярные языки и грамматики
Автоматные регулярные грамматики
К регулярным грамматикам относятся
Системное программное обеспечение
Регулярные языки и грамматики
Автоматные регулярные грамматики
К регулярным грамматикам относятся
леволинейные грамматики G(VT,VN,P,S), V=VN∪VT
праволинейные грамматики 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
Системное программное обеспечение
Регулярные языки и грамматики
Схема алгоритма преобразования
регулярной грамматики
к автоматному
Системное программное обеспечение
Регулярные языки и грамматики
Схема алгоритма преобразования
регулярной грамматики
к автоматному
для правила 3: S→Ba) во множество VN'=VN'∪{S2}, в множество Р'
для правила 3: S→Ba) во множество VN'=VN'∪{S2}, в множество Р'
добавляются правила: S→ S2), S2→Ba
для правила 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.