FORM LN JAZYKY A AUTOMATY I
Re en cvicen 5.
1. Hledan automat je urcen n sleduj c m grafem:
12
23
3
2
2
1
2
2,3
2
2. G = (fS; X; Yg; fa; b; c; dg; P; S),pricem mno ina pravidel P obsahuje n sleduj c pravidla:
P : S ! XSY j XY
X ! aXb j aabb
Y ! cYd j ccdd
3. Rozli me dva pr pady: bud' juj 6= jvj, anebo juj = jvj; u = u1; : : : ; uk, v = v1; : : : ; vk a
existuje i takov , e ui 6= vi. Slova prvn ho typu budeme generovat z netermin lu S1; slova
druh ho typu z netermin lu S2.
G = (fS; S1; S2; S1L; S1PSRg; fa; b; cg; P; S), pricem mno ina pravidel P obsahuje n sleduj c
pravidla:
P : S ! S1 j S2
S1 ! xS1y j xS1L j S1Px
S1L ! xS1L j c
S1P ! S1Px j c
S2 ! aS2a j bS2b j aSRb j bSRa
SR ! xSRy j c
pro v echna x; y 2 fa; bg
1