IB102 ­ úkol 9 ­ řešení Odevzdání: 1. 12. 2008
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [2 body] Následující bezkontextovou gramatiku převedťe do Chomského normální formy
pomocí postupu uvedeného na přednášce:
G = ({S, A, B, C}, {a, b, c}, P, S), kde
P = { S  C | aB | AB,
A  aa | BC | ABC | aAbCc,
B  Ca | C | b,
C   | C | aBc }
Řešení: Gramatika je bez nepoužitelných neterminálů. Před převodem do CNF musíme
nejprve odstranit -pravidla a jednoduchá pravidla.
Odstranění -pravidel:
N = {S, A, B, C}
Ekvivalentní gramatika bez -pravidel: G = ({S , S, A, B, C}, {a, b, c}, P , S ), kde
P = { S   | S,
S  a | A | B | C | aB | AB,
A  A | B | C | aa | AB | AC | BC | abc | ABC | abCc | aAbc | aAbCc,
B  a | b | C | Ca,
C  C | ac | aBc }
Odstranění jednoduchých pravidel:
NS = {S , S, A, B, C}, NS = {S, A, B, C}, NA = {A, B, C}, NB = {B, C}, NC = {C}
Ekvivalentní gramatika bez jednoduchých pravidel: G = ({S , S, A, B, C}, {a, b, c}, P , S ),
kde
P = { S   | a | b | aa | ac | aB | Ca | AB | AC | BC | aBc | abc | ABC | abCc | aAbc | aAbCc,
S  a | b | aa | ac | aB | Ca | AB | AC | BC | aBc | abc | ABC | abCc | aAbc | aAbCc,
A  a | b | aa | ac | Ca | AB | AC | BC | aBc | abc | ABC | abCc | aAbc | aAbCc,
B  a | b | ac | Ca | aBc,
C  ac | aBc }
Převod do CNF: Ekvivalentní gramatika v CNF:
G = ({S , S, A, B, C, a , b , c , BC , Bc , bc , bCc , Cc , Abc , AbCc }, {a, b, c}, P , S ),
kde
P = { S   | a | b | a a | a c | a B | Ca | AB | AC | BC | a Bc | a bc | A BC
| a bCc | a Abc | a AbCc ,
S  a | b | a a | a c | a B | Ca | AB | AC | BC | a Bc | a bc | A BC
| a bCc | a Abc | a AbCc ,
A  a | b | a a | a c | Ca | AB | AC | BC | a Bc | a bc | A BC
| a bCc | a Abc | a AbCc ,
B  a | b | a c | Ca | a Bc ,
C  a c | a Bc ,
a  a,
b  b,
c  c,
bc  b c ,
BC  BC,
Bc  Bc ,
bCc  b Cc ,
Cc  Cc ,
Abc  A bc ,
AbCc  A bCc }
IB102 ­ úkol 9 ­ řešení Odevzdání: 1. 12. 2008
Vypracoval: James Bond UČO: 007
Skupina: MI6
2. [2 body] Dokažte, že jazyk L = {a(n2)
| n > 0} není bezkontextový. Použijte pumping
lemma pro bezkontextové jazyky.
Řešení:
1. nechť n je libovolné nezáporné celé číslo
2. zvolme slovo z = an2
 L
3. uvažme všechny možnosti, jak lze slovo z zapsat jako z = uvwxy tak, aby vx = ,
|vwx|  n:
Označme si |vx| = g.
4. Vezměme slovo uv2
wx2
y. Toto slovo má délku n2
+g. Ale nejbližší vyšší druhá mocnina
nějakého přirozeného čísla ­ (n+1)2
­ je od n2
vzdálena alespoň (n+1)2
-n2
= 2n+1.
Protože |vwx|  n, tak g  n. Tedy i g < 2n + 1, proto n2
+ g není druhá mocnina
žádného přirozeného čísla. Slovo uv2
wx2
y nepatří do jazyka L.