2 типі. G = (VT,VN,P,S) грамматикасы контекстно-бос грамматика деп аталады (КС-грамматикасы), егер де оның ережесі мынадай түрді қамтыса: A → β, AVn және β V*
3 типі. Грамматика G = (VT, VN, P, S) сол жақ терістігінің жүйелік грамматикасы (Р-грамматикасы), егер де оның ережесі мынадай түр қамтыса A → aB | a , мұндағы a VT; A, BVN.
Грамматика G = (VT, VN, P, S) оң жақ терістігінің жүйелік грамматикасы (Р-грамматикасы), егер де оның ережесі мынадай түр қамтыса A → aB | a , мұндағы a VT; A, BVN.
Анықтама 1.12. L(G) тілін деп k тілін айтамыз, егер де оны k грамматика типінде жаткызсақ, k - грамматика типінің максималды мүмкіншілік нөмірі. Арақатынас грамматика типтері және тілдер 1.1 суретте көрсетілген.
Р - жүйелі грамматика ;
КС - контекстно-бос грамматика;
КЗ - контекстно-тәуелді грамматика;
0 типті - грамматика 0 типі.
1.1 сурет - Арақатынас грамматика типтері және тілдер
Мысал 1.6. Хомский классификациясының әртүрлі фомалды түрлер және грамматика мысалдары. Терминалдарды мәтіндік жол символдарымен белгілейміз, терминалды емес – жазылған әріппен, бастапқы символ грамматикасы - S.
n2−1
а) Тіл түрі 0 L(G)={ a2 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 → ε
б) Контекстно-тәуелді тіл L(G)={anbncn | n≥1} шығару ережесімен грамматика анықталады:
1) S → aSBC | abc; 2) bC → bc;
3) CB → BC; 4) cC → cc;
5) BB → bb.
в) Контекстно-бос тілдер L(G)={(ab)n(cb)n | n>0 } S → шығару ережесімен грамматика анықталады:
Q → cSc.
2) Q → cSc.
г) Жүйелі тіл L{G)={col| ω {a, b}+, а} шығару ережесімен грамматика анықталады:
1) S → A | B ;
2) A → a | Ba;
3) B → b | Bb | Ab.
№ 1 зертханалық жұмысқа орындау тапсырмалары
Зертханалық жұмысты орындаған кезде келесі іс-әрекеттерді орындау қажет:
грамматикаларды құру, тудырушы формальды тілдер, берілген нұсқаларымен сәйкестігі;
Хомский классификацисясындағы формалды грамматика типтері мен тілдерді анықтау;
3) программалық құрылымды қамсыздандыру, Хомский классификациясындағы берілген өрістерді тану типі.
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}+}
|
Достарыңызбен бөлісу: |