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



жүктеу 14,81 Mb.
бет101/127
Дата21.05.2018
өлшемі14,81 Mb.
#15467
1   ...   97   98   99   100   101   102   103   104   ...   127

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 → шығару ережесімен грамматика анықталады:

  1. Q → cSc.

2) Q cSc.

г) Жүйелі тіл L{G)={col| ω {a, b}+, а} шығару ережесімен грамматика анықталады:

1) S A | B ;

2) A a | Ba;

3) B b | Bb | Ab.

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

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



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

  2. Хомский классификацисясындағы формалды грамматика типтері мен тілдерді анықтау;

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}+}

жүктеу 14,81 Mb.

Достарыңызбен бөлісу:
1   ...   97   98   99   100   101   102   103   104   ...   127




©g.engime.org 2024
әкімшілігінің қараңыз

    Басты бет
рсетілетін қызмет
халықаралық қаржы
Астана халықаралық
қызмет регламенті
бекіту туралы
туралы ережені
орталығы туралы
субсидиялау мемлекеттік
кеңес туралы
ніндегі кеңес
орталығын басқару
қаржы орталығын
қаржы орталығы
құрамын бекіту
неркәсіптік кешен
міндетті құпия
болуына ерікті
тексерілу мемлекеттік
медициналық тексерілу
құпия медициналық
ерікті анонимді
Бастауыш тәлім
қатысуға жолдамалар
қызметшілері арасындағы
академиялық демалыс
алушыларға академиялық
білім алушыларға
ұйымдарында білім
туралы хабарландыру
конкурс туралы
мемлекеттік қызметшілері
мемлекеттік әкімшілік
органдардың мемлекеттік
мемлекеттік органдардың
барлық мемлекеттік
арналған барлық
орналасуға арналған
лауазымына орналасуға
әкімшілік лауазымына
инфекцияның болуына
жәрдемдесудің белсенді
шараларына қатысуға
саласындағы дайындаушы
ленген қосылған
шегінде бюджетке
салығы шегінде
есептелген қосылған
ұйымдарға есептелген
дайындаушы ұйымдарға
кешен саласындағы
сомасын субсидиялау