FORM LN JAZYKY A AUTOMATY I
Re en cvicen 9.
1. a)Bud'Lregul rn jazykakceptovan deterministick mkonecn mautomatemA = (K; ; ; P; F).
Navrhneme z sobn kov automat M pro jazyk Q (M akceptuje pr zdn m z sobn kem).
M = (fq; q jq 2 Kg; ; fZ0; Zg; ; P; Z0; ;), kde
: (q; x; Z0) = f( (q; x); ZZ0)g pro v echna q 2 K;x 2
(q; x; Z) = f( (q; x); ZZ)g pro v echna q 2 K;x 2
(q; ]; Z) = f(P; Z)g pro v echna q 2 F
(P; ]; Z0) = f(P; ")g za podm nky, e P 2 F
(q; x; Z) = f( (q; x); ")g pro v echna q 2 K;x 2
(q; "; Z0) = f(q; ")g pro v echna q 2 F
b) Nen . Stac vz t napr. bezkontextov jazyk L = fanbn j n > 0g. Aby pri napumpov van
byl zachov n vztah mezi d lkou slov u a v mus b t jeden vkl dan retezec podretezcem
slova u a druh podretezcem slova v. Av ak slovo anbn nen mo n napumpov vat jenom
na jednom m ste viz pumping lema pro regul rn jazyky.
2. L(M) = fanbn j n 1g
3. Bez jmy na obecnosti lze predpokl dat, e automat A = (K; ; ; ; q0; Z; ;) akceptuj c
jazykLakceptujepr zdnoupamet a epoc tecn z sobn kov symbolZsevprvn mkroku
v poctu vybere ze z sobn ku a v dal m prubehu v poctu se tam ji nikdy neobjev .
De nujeme nov automat Aakceptuj c jazyk L1997 takto: automat Avlo v prvn m kroku
sv ho v poctu do z sobn ka 1997 symbolu Z. Kdykoliv se v prubehu v poctu objev na
vrcholuz sobn kasymbol Z,znamen to, eautomatAakceptoval.Proto automatAzacne
znovu simulovat cinnost automatu Aod poc tecn ho stavu.
Bud'te J; r nov symboly, J 62 a r 62 K.
A = (K frg; ; fJg; ; r; J; ;)
(r; "; J) = f(q0; Z1997)g
(p; x; y) = (p; x; y) pro v echna p 2 K; x 2 ; y 2
(p; "; Z) = f(q0; Z)gpro v echna p 2 K.
1