IB 102 - úkol 8, příklad 2 - řešení
Odevzdání: 12.11. 2012
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [2 body] Uvažme bezkontextovou gramatiku Q = ({S}, {a, b}, P, S), kde
P = {S —> aaSb | aab}.
Navrhněte bezkontextovou gramatiku Q', která generuje všechny prefixy všech slov generovaných gramatikou Q, tj. takovou, že L(Q') = {u G {a,b}* | 3v G {a, b}*, kde uv G L(Q)}.
Rešení: Gramatika Q generuje jazyk L(Q) = {a2nbn | n > 1}. Naším cílem je tedy najít gramatiku Q', která generuje jazyk L(Q') = {a2nbm | n > 1 Am < n}U{an \ n > 0}. Řešením je gramatika Q1 = ({S', A, B}, {a, b}, P', S'), kde
P' = {S' -> A | B, A^ř aA\ e, B —y aaBb | aaB \ e}.
Pozn.: Využili jsme zavedené konvence, že bezkontextové gramatiky mohou obsahovat e-pravidla.