Véges automata determinizálása, összefüggő automaták, algoritmikus eldöntési probléma

5. Véges automata determinizálása, összefüggő automaták, algoritmikus eldöntési probléma

Véges automata determinizálása

Minden $A = ⟨ Q, Σ, δ, Q_{0}, F ⟩$ véges nemdeterminisztikus automatához megkonstruálható egy $A^{'} = ⟨ Q^{'}, Σ, δ^{'}, q_{0}^{'}, F^{'} ⟩$ véges determinisztikus automata úgy, hogy $L (A) = L (A^{'})$ teljesül.

L3 további zártsági tulajdonságia

$L_{3}$ zárt a komplementerre, a metszetre és a különbségre.

Tehát az alábbi formális eszközök mind az $L_{3}$ nyelvosztályt írják le egy adot ábécé felett:

jobblineáris grammatikák
ballineáris grammatikák
3-as normálformájú grammatikák
reguláris kifelyezések
a komplementer, metszet, különbség, tükörkép, pozitív lezárt műveletekkel bővített úgynevezett általánosított kifejezések
véges determinisztikus automaták
véges nemdeterminisztikus automaták

Összefüggő automata

Legyen $A = ⟨ Q, Σ, δ, q_{0}, F ⟩$ véges determinisztikus automata. A $q$ állapotot a kezdőállapotból elérhetőnek mondjuk, ha létezik $q_{0} x ⟹ q$ redukció, ahol $x \in Σ^{*}$

Az $A = ⟨ Q, Σ, δ, q_{0}, F ⟩$ véges determinisztikus automatát összefüggőnek mondjuk, ha minden állapota elérhető a kezdőállapotból.

$q$ elérhető a kezdőállapotból, akkor és csak akkor, ha van olyan $x \in Σ^{*}$ , hogy $δ (q_{0}, x) = q$

Algoritmikus problémák

Akkor beszélünk algoritmukis eldöntési problémáról, ha a bemenet egy olyan objektum, mely egy adott végtelen halmazból kerülhet ki, kimenete pedig igen/nem.

Olyan algoritmust keresünk, amely kellően általános ahhoz, hogy a végtelen lehetséges bemenet bármelyike esetén alkalmazható legyen.

Egy probléma eldönthető, ha létezik olyan minden lehetséges bemenet esetén termináló algoritmus, amelyik a helyes választ adja.

3as típusú grammatikák algoritmikus problémái

Eldönthető, hogy egy reguláris grammatika az üres nyelvet generálja-e.

Bizonyítás: A tanultak szerint a grammatikához megadható olyan A véges determinisztikus automata, amelyik a grammatika által generált nyelvet ismeri fel. Az automata pontosan akkor nem ismer fel egyetlen szót sem, ha kezdőállapotából minden végállapota elérhetetlen. Ez viszont algoritmikusan eldönthető.

Eldönthető, hogy két reguláris grammatika által generált nyelv diszjunkt-e.

Bizonyítás: Generálják a $G_{1}$ és $G_{2}$ reguláris grammatikák rendre az $L_{1}$ és $L_{2}$ nyelveket. Az $L_{3} = (L_{1} \cap L_{2}) \cup (L_{1} \cap L_{2})$ nyelv szintén reguláris, így van olyan $G_{3}$ reguláris grammatika, amely $L_{3}$ -at generálja. Ekkor azonban $L_{1} = L_{2}$ akkor és csak akkor, ha $L_{3} = \emptyset$ , amely a fentiek szerint eldönthető.

Eldönthető, hogy két reguláris grammatika ugyanazt a nyelvet generálja-e vagy sem.

Bizonyítás: Generálják a $G_{1}$ és $G_{2}$ reguláris grammatikák rendre az $L_{1}$ és $L_{2}$ nyelveket. Az $L_{3} = (L_{1} \cap \overset{ˉ}{L}_{2}) \cup (\overset{ˉ}{L}_{1} \cap L_{2})$ nyelv szintén reguláris, így van olyan $G_{3}$ reguláris grammatika, amely $L_{3}$ -at generálja. Ekkor azonban $L_{1} = L_{2}$ akkor és csak akkor, ha $L 3 = \emptyset$ , amely a fentiek szerint eldönthető.

Eldönthető, hogy egy reguláris grammatika bővebb, vagy egyenlő nyelvet generál-e, mint egy másik.

Bizonyítás: Generálják a $G_{1}$ és $G_{2}$ reguláris grammatikák rendre az $L_{1}$ és $L_{2}$ nyelveket. Az $L_{3} = (L_{1} \cap \overset{ˉ}{L}_{2}) = L_{1} ∖ L_{2}$ szintén reguláris. Ennek üressége eldönthető, ami ekvivalens azzal, hogy $L_{1} \subseteq L_{2}$

A 3-as típusú grammatikák szóproblémája hatékonyan eldönthető.

Szóprobléma: Adott $G$ grammatika és $u \in Σ^{*}$ . $u \in ? L (G)$

Bizonyítás: Legyen $G = ⟨ N, Σ, P, S ⟩$ egy 3-as típusú grammatika normálformában adva és $u = t_{1} \dots t_{n}$ a levezetendő szó.

Az algoritmus rekurzívan kiszámol egy $N$ részhalmazból álló $H_{i} (0 \leq i \leq n)$ sorozatot. $H_{i}$ -ból $H_{i + 1}$ (csak $G$ -től függő) konstans időben számolható.

$H_{0} : = {S}, H_{i + 1} : = {A \in N ∣\exists B \in H_{i} \land B \to t_{i + 1} A \in P}$

Könnyen látható, hogy $H_{i}$ azon nemterminálosok halmaza, melyek pontosan $i$ leezetési lépés után a mondatforma végén állhatnak.

Tehát ha $F = {A \in N ∣ A \to ϵ \in P}$ , akkot nyilván $u \in L (G) ⟺ H_{n} \cap F \neq = \emptyset$

4. félévi jegyzetek

Véges automata determinizálása, összefüggő automaták, algoritmikus eldöntési probléma