«Соңғы автоматтар және формальдік тілдер теориясы»

Р - жүйелі грамматика ;

КС - контекстно-бос грамматика;

КЗ - контекстно-тәуелді грамматика;

Мысал 1.6. Хомский классификациясының әртүрлі фомалды түрлер және грамматика мысалдары. Терминалдарды мәтіндік жол символдарымен белгілейміз, терминалды емес – жазылған әріппен, бастапқы символ грамматикасы - S.

а) Тіл түрі 0 L(G)={ a² b | n ≥1} шығару ережесімен грамматика анықталады:

1) S → aaCFD; 2) AD → D;

3) F → AFB | AB; 4) Cb → bC;

5) AB → bBA; 6) CB → C;

7) Ab → bA; 8) bCD → ε

1) S → aSBC | abc; 2) bC → bc;

1. 
   Q → cSc.
   

1) S → A | B ;

2) A → a | Ba;

3) B → b | Bb | Ab.

№ 1 зертханалық жұмысқа орындау тапсырмалары

Зертханалық жұмысты орындаған кезде келесі іс-әрекеттерді орындау қажет:

1. 
   грамматикаларды құру, тудырушы формальды тілдер, берілген нұсқаларымен сәйкестігі;
   
2. 
   Хомский классификацисясындағы формалды грамматика типтері мен тілдерді анықтау;
   

1.1 кесте - № 1 зертханалық жұмыстағы жеке тапсырма нұсқамасы

Нұсқа	Формалды тіл
1	L(G)={anbmck		n, m, k>0}
2	L(G)={(ab)n(cb)m			n, m≥
3	L(G)={0n(10)m		n, m≥
4	L(G)={wcwcw		w{a,b}+}
5	L(G)={c2ndn	n>0}
6	L(G)= {l+l-l	lG{a,b}+}
7	L(G)={(10)n-1(01)n+1 n>0}
8	L(G)={(ac)	n>0, a {b, d}, c{+, -}}
9	Z(G)={ (010)w			n>0}
10	L(G)={a1a2…anan…a2a1				ai {0, 1}}
11	L(G)={a1a2…ana1a2…an				ai {c, d}}
12	L(G)={ab.b	ai {+, -}, b {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}+}