Pokročilé úlohy pre tvorbu gramatík

Táto stránka bude venovaná iba riešeným úlohám pre tvorbu gramatík z hľadiska formálnych jazykov. Najskôr sa ich pokús vyriešiť sám, potom si riešenie skontroluj. Alebo iba sleduj...

Regulárne gramatiky

Predpokladá sa, že výsledné riešenie bude definícia regulárnej gramatiky, definovaná ako $G = (N, T, P, S)$ .

1.

Zadanie: Navrhnite regulárnu gramatiku, ktorá generuje jazyk $L = {x \in N; n \geq 255}$ .

Riešenie

Odporúčané je skamarátiť sa s matematickými zápismi. Zadanie chce všetky prirodzené čísla (to znamená, čísla väčšie ako nula) ktoré sú zároveň väčšie alebo rovné ako 255. To znamená, že hľadáme čísla: 255, 256, 257, 258, 259, 260 a tak ďalej, až donekonečna... V zadaní je zároveň požiadavka, že sa má jednať o regulárnu gramatiku - teda, pravidlá musia byť zapísané vo forme, kde na ľavej strane je práve jeden neterminálny symbol a na pravej strane jeden terminálny symbol za ktorým nasleduje práve jeden neterminálny symbol.

Jedno z mnohých riešení by mohlo vyzerať napríklad takto:

$\begin{aligned} P : \\ S & \to 1 c_{1} | 2 d | 3 c_{2} | 4 c_{2} | \dots | 9 c_{2} \\ c_{1} & \to 0 c_{2} | 1 c_{2} | \dots | 9 c_{2} \\ c_{2} & \to 0 c_{3} | 1 c_{3} | 2 c_{3} | \dots | 9 c_{3} \\ c_{3} & \to 0 c_{3} | 1 c_{3} | \dots | 9 c_{3} | 0 | 1 | 2 | \dots | 9 \\ d & \to 0 c_{2} | 1 c_{2} | 2 c_{2} | 3 c_{2} | 4 c_{2} | 5 c_{2} | 6 c_{3} | \dots | 9 c_{3} | 5 p \\ p & \to 5 | 6 | 7 | 8 | 9 \end{aligned}$