Příklad 1. Dokažte nebo vyvraťte, že následující jazyky jsou regulární a) nad abecedou (a): L1={a^p | p je prvočíslo} b) nad abecedou (a,b): L2={w | w obsahuje stejný počet slov "ab" a "ba"} c) jako b), ale nad abecedou (a,b,c) Řešení: a) Sporem: Nechť m je index kongruence ~ z Nerodovy věty. Nalezneme taková sousedící prvočísla p < q jejichž rozdíl je větší než m. Pak alespoň dvě ze slov a^p+1 ... a^q spadnou do stejné třídy ekvivalence, čili a^i ~ a^j i<>j. Připojme k nim slovo a^q-i. Potom a^i je prvkem L1, ale a^j obecně ne, což je spor. b) Je regulární - je rozpoznatelný konečným automatem a b 1 1 3 2 1 2 In/Out 3 2 4 4 4 5 5 3 5 c) Sporem: Nechť m je index kongruence ~ z Nerodovy věty. Mějme slova (abc)^l pro l=1,...,m+1. Aspoň dvě z nich spadnou do stejné třídy ekvivalence, čili (abc)^i ~ (abc)^j i<>j. Připojme k nim slovo (bac)^i: (abc)^i(bac)^i ~ (abc)^j(bac)^i, což je spor, protože první z nich je prvkem L3, ale druhé ne. Příklad 3. K regulárnímu výrazu (a(ab*a)*a)+lambda zkonstruujte a) zobecněný nedeterministický automat b) deterministický automat c) redukovaný automat Řešení: a) - očíslujeme symboly regulárního výrazu: (a1(a2b3*a4)*a5)+lambda - páry, které se mohou vyskytovat za sebou: 12, 15, 23, 24, 33, 34, 42, 45. - symboly, které mohou být první ve slově: 1 - symboly, které mohou být poslední ve slově: 5 - zahrnuje prázdné slovo? : ANO a b In/Out S {1} {} 1 {2,5} {} 2 {4} {3} 3 {4} {3} 4 {2,5} {} Out 5 {} {} b) převod na deterministický automat a b In/Out {S} {1} {} {1} {2,5} {} Out {2,5} {4} {3} {4} {2,5} {} {3} {4} {3} {} {} {} a b In/Out A B F B C F Out C D E D C F E D E F F F c) redukce a b R1 a b R2 a b R3 a b R4 a b In/Out A B F II I I II III I II III I V III I B C F I II I III II I III II I III II I Out C D E II I I II III I II III IV II III IV D C F I II I III II I III II I III II I E D E I I I I III I IV III IV IV III IV F F F I I I I I I I I I I I I Stavy B a D jsou ekvivalentní, takže jejich sjednocením dostaneme redukovaný automat. Příklad 4. Dokažte anebo vyvraťte a) L1\(L2 průnik L3) je nadmnožinou ((L1\L2) průnik (L1\L3)) b) L1\(L2 průnik L3) je podmnožinou ((L1\L2) průnik (L1\L3)) c) derivace_podle_w(Sigma*-L) = Sigma* - derivace_podle_w(L) Řešení: a) Neplatí - protipříklad L1={ab, ba}, L2={baba}, L3={abba} => LEVÁ={}, PRAVÁ={ba} b) (1) Nechť v je prvkem LEVÁ. Pak platí (přepis): existuje u prvkem L1: uv prvkem L2 & uv prvkem L3. (2) Nechť w je prvkem PRAVÁ. Pak platí (přepis): existují t,u prvky L1: tv prvkem L2 & uv prvkem L3. (1) je zvláštní případ (2), kde t=u, tudíž LEVÁ je podmožinou PRAVÁ. c) LEVÁ je podmožinou PRAVÁ?: Nechť x prvkem LEVÁ. Pak platí: existuje w takové, že wx prvkem Sigma*-L. wx prvkem Sigma*-L => wx není prvkem L => x není prvkem derivace_podle_w(L) => x je prvkem PRAVÁ PRAVÁ je podmnožinou LEVÁ?: Nechť x prvkem PRAVÁ. Pak platí: x není prvkem derivace_podle_w(L). x není prvkem derivace_podle_w(L) => wx není prvkem L pro všechna w => wx je prvkem Sigma*-L => x prvkem LEVÁ Příklad 5. a) Vytvořte regulární výraz popisující právě všechna slova nad (a,b), ve kterých je každý maximální úsek a-ček sudé délky. b) Zderivujte ho podle a, b, ab. c) vytvořte redukovaný deterministický konečný automat Řešení: a) (b*(aa)*)* b) derivace podle a = a((aa)*b*)* derivace podle b = (b*(aa)*)* derivace podle ab = prázdná množina c) (b*(aa)*)* 1 23 - páry, které se mohou vyskytovat za sebou: 11, 12, 23, 32, 31 - symboly, které mohou být první ve slově: 1, 2 - symboly, které mohou být poslední ve slově: 1, 3 - zahrnuje prázdné slovo? : ANO a b In/Out S 2 1 Out 1 2 1 2 3 Bot Out 3 2 1 Bot Bot Bot Redukcí dostaneme: a b In/Out S 1 S 1 S Bot Bot Bot Bot Příklad 6. K automatu zkonstruujte regulární výraz. a b In 1 2 1 2 2 3 Out 3 2 1 Řešení: (b*a(a*ba)*a*bb)*b*a(a*ba)*a*b