Rozhodnutelnost problémů podle tříd jazyků Problém Reg DCF CF CS Rec RE Je Z.(9) prázdný? Je Z.(9) konečný? JeL(S) = I*? JeL(S) =/?(/? je regulární)? JeL(S1)=i(g2)? Je/.(9i)cag2)? Je L(9) regulární? R = rozhodnutelný N = nerozhodnutelný ano = algoritmus vždy vrátí ano IB005 Formální jazyky a automaty 1,17.5.2016 1/16 Rozhodnutelnost problémů podle tříd jazyků Problém Reg DCF CF CS Rec RE Je průnik dvou jazyků téhož typu? Je sjednocení dvou jazyků téhož typu? Je komplement jazyka téhož typu? Je zřetězení dvou jazyků téhož typu? Je gramatika S víceznačná? R = rozhodnutelný N = nerozhodnutelný ano = algoritmus vždy vrátí ano IB005 Formální jazyky a automaty 1,17.5.2016 Problém prázdnosti Věta 5.23. Problém prázdnosti pro třídu bezkontextových gramatik je rozhodnutelný. Důkaz. Je obsažen v důkazu věty 3.9. IB005 Formální jazyky a automaty 1,17.5.2016 Postův korespondenční problém (připomenutí) Postův korespondenční problém. Pro dané dva seznamy slov A = (x-i,..., xn) b = (yi—yn) rozhodnout, zda existují čísla /n,..., taková, že Xj^Xj2... Xjk = y^yj2 ■ ■ ■ yjk■ Dvojici (A, B) nazýváme instancí PCP. Čísla /n,..., nazýváme řešením této instance PCP. PCP je nerozhodnutelný. IB005 Formální jazyky a automaty 1,17.5.2016 4/16 Problém prázdnosti Věta 5.25. Problém prázdnosti pro třídu kontextových gramatik je nerozhodnutelný. Důkaz. Redukujeme problém na doplněk PCP. Bud dána instance PCP A = (x1f... ,xn), B = (y1f... ,yn) nad abecedou I. Uvažme jazyky , def LA = . def LB = nad abecedou Iu{#,i,...n}. Jazyk LA n LB je kontextový a je prázdný právě tehdy pokud instance (A, B) nemá řešení: Redukce instanci (A, B) přiřadí CS gramatiku g generující jazyky n LB. IB005 Formální jazyky a automaty 1,17.5.2016 Problém konečnosti Věta 5.27. Problém konečnosti pro třídu bezkontextových gramatik je rozhodnutelný. Důkaz. Jako důsledek lemmatu o vkládání pro CFL víme, že L(S) je nekonečný právě tehdy, když obsahuje slovo z délky p < |z| ^ p + q. □ IB005 Formální jazyky a automaty 1,17.5.2016 Problém konečnosti Věta 5.28. Problém konečnosti pro třídu kontextových gramatik je nerozhodnutelný. Důkaz. Pokud má PCP řešení, má jich nekonečně mnoho: Tedy jazyky n LB je konečný právě tehdy, pokud instance (A, B) PCP řešení. IB005 Formální jazyky a automaty 1,17.5.2016 Pár pomocných jazyků Bucív4 = (x1f... ,xn), B = (y1f... ,yn) instance PCP. Definujeme def LA = {x-h ...xik#ik...i, I k > i a i ^ /) ^ n pro každé i < y < n] def = {yi, ■ ■ ■ y/^#//c ■ ■ ■ /'i I k ^ i a i ^ /) n lze napumpovávat. Protože L je neprázdný, je , můžeme tedy zvolit slovo z = xh... xik#ik ... ... ik#Yik ■ ■ ■ y u pro k ^ n. Pro žádné rozdělení z na části u, v, w,x,y splňující podmínky PL ale neplatí uv2wx2y g /-, což je spor. □ IB005 Formální jazyky a automaty 1,17.5.2016 11/16 Problém rovnosti s daným regulárním jazykem Věta 533 a). Pro danou bezkontextovou gramatiku S a daný regulárni jazyk R je nerozhodnutelné určit, zda /.(S) = /?. Důkaz. Stačí zvolit za S gramatiku pro jazyk co—{LAiB n S) a «=(Zu{#}u{i...n})*. Pak /.(S) = /? právě tehdy, když instance (A, B) nemá řešení. IB005 Formální jazyky a automaty 1,17.5.2016 □ 12/16 Problém inkluze s daným regulárním jazykem Věta 533 b). Pro danou bezkontextovou gramatiku S a daný regulární jazyk R je nerozhodnutelné určit, zda L[S) 2 /?. Důkaz. Víme, že rozhodnout, zda L(S) = R, není rozhodnutelné. Stačí ukázat, že rozhodnout, zda L(S) c R, je rozhodnutelné. To je ale jednoduché, protože L[S) c /? platí právě tehdy, když jazyk je prázdný. Tento jazyk je ale bezkontextový. □ IB005 Formální jazyky a automaty 1,17.5.2016 13/16 Problémy rovnosti Věta 5*34* a) Pro danou bezkontextovou gramatiku S s terminálni abecedou I je nerozhodnutelné určit, zda /.(S) = I*. b) Pro dané bezkontextové gramatiky a S2 je nerozhodnutelné určit, zda Důkaz. a) Stačí za S vzít gramatiku generující jazyk b) Stačí za Sn vzít gramatiku generující jazyk a za S2 gramatiku generující jazyk IB005 Formální jazyky a automaty 1,17.5.2016 □ 14/16 Problémy bezkontextovosti a regularity Věta 535. Pro dané bezkontextové gramatiky a S2 je nerozhodnutelné určit, zda a) /.(Si) n /.(S2) je bezkontextovýjazyk, b) co—/.(St) je bezkontextový jazyk, c) /-(Si) je regulárni jazyk. Důkaz. a) Stačí zvolit bezkontextové gramatiky a g2 takové, že /-(Si) = LÍS2) = b) Stačí zvolit bezkontextovou gramatiku S takovou, že Z.(Sn) = c) To samé jako v b). IB005 Formální jazyky a automaty 1,17.5.2016 15/16 Problém víceznačnosti Věta 5.36. Pro danou bezkontextovou gramatiku g je nerozhodnutelné určit, zdaje víceznačná. Důkaz. Bud A = (x1f... ,xn), B = (yn,... ,yn) instance PCP. Zvolme gramatiku S s pravidly Páá{s ->s, is2l 52^ } Pak gramatika S je víceznačná právě tehdy, když instance (A, B) má řešení. □ IB005 Formální jazyky a automaty 1,17.5.2016 16/16