Граматиканың қай түрі

2-межелік бақылау тапсырмасы

Төмендегі тапсырмалар формальды тілдер, тізбектер және грамматикалар тақырыптарын қайталауға арналған. Жауаптарыңызда анықтамаларды нақты беріп, қажетті жерлерде дәлелдеу қадамдарын көрсетіңіз.

1) Формальды анықтама құру

Теориялық бөлім

Келесі ұғымдарды құру үшін тілдің формальды анықтамасын беріңіз (әліпби, тізбектер жиыны және қажет болса шектеулер көрсетілсін):

а) Оң бүтін сандар жиыны.
b) Қазақ тіліндегі сөздер жиыны.
c) Программалау тілдеріндегі идентификаторлар жиыны.

Ескерту: Идентификатор үшін, әдетте, бірінші символ әріп немесе астыңғы сызық болуы мүмкін, ал қалғандары әріптер, цифрлар және астыңғы сызықтардан тұрады (нақты ережені өзіңіз формальды түрде бекітіңіз).

2) Тізбектерді құрастыру және сипаттау

Тәжірибелік бөлім

Әліпби

V_T = { 0, 1, 2 }

Берілген тізбектер

α = 01

β = 2

γ = 011

Талап

Тізімді жазып, әрқайсысының ұзындығын, басын және соңын сипаттаңыз.

Келесі тізбектерді жазыңыз

1) αβ

Құрастыру, ұзындығы, басы, соңы.
2) βα

Құрастыру, ұзындығы, басы, соңы.
3) αβγ

Құрастыру, ұзындығы, басы, соңы.
4) α⁴

Қайталану арқылы құрастыру.
5) α⁴β²

Қайталану және жалғау (конкатенация) ережелерімен.

Нұсқау: Ұзындықты |w| түрінде белгілеңіз, ал тізбектің басы мен соңын (бірінші және соңғы символдарын) нақты көрсетіңіз.

3) Грамматика және туындатуды тексеру

Дәлелдеу

Келесі грамматика берілсін: G = (V_T, V_N, P, J), мұнда:

Жиындар

V_T: = { a, b, c }
V_N: = { A, B, J }
J: ∈ V_N (бастапқы символ)

Өндіріс ережелері (P)

p1: J → aB
p2: B → A
p3: B → b
p4: A → c

Туындату ақиқаттығын (true/false) дәлелдеңіз

Әрбір тұжырым үшін грамматика ережелері арқылы туындатуға болатынын немесе болмайтынын көрсетіңіз (қадам-қадамымен немесе қарсы дәлелмен).

a) J ⇒* a
b) J ⇒* ac
c) B ⇒* Ac
d) aJ ⇒* aab
e) aBb ⇒* acb

Қосымша сұрақ: Бұл грамматика Хомский иерархиясы бойынша қай түрге жатады? Жауабыңызды ережелердің құрылымымен негіздеңіз.