Bc. Jan Kaláb <[email protected]>
Uvažte jazyk L1 = {aibj | 0 < i ≤ j ∧ i + j = 2k, k ∈ ℕ}.
Sestavte gramatiku G1 takovou, že L(G1) = L1.
G1 = ({a, b}, {S, X, Y}, S, P)
P = {
}
Jakého typu (dle Chomského hierarchie jazyků) je G1 a jakého typu je L1? Mohou se tyto typy obecně lišit? Svoje tvrzení zdůvodněte.
G1 je typu 2, tedy bezkontextová, protože obsahuje pravidla ve tvaru A → γ, A ∈ N, γ ∈ (N ∪ Σ). Jazyk L1 navíc potřebuje „počítat“, takže jistě nepůjde popsat omezenějším typem, než 2, protože ono „počítání“ potřebuje zásobník.
L1 je tedy podle definice 2.16 z opory (nebo 1.10 ze slajdů) také typu 2, tedy bezkontextový.
Obecně mohou. Tento jazyk by jistě bylo možno popsat i gramatikou typu 0, ale stále by to byl stejný (typu 2) jazyk. Je ale zvykem, že se typ jazyka i gramatiky shoduje.
Uvažte regulární výraz r2 = (ab + ε)* a* c.
Převeďte r2 algoritmicky na redukovaný deterministický konečný automat M2 (tj. RV → RKA → DKA → redukovaný DKA), přijímající jazyk popsaný výrazem r2.
Podle algoritmů 3.4, 3.5 a 3.7 z opory.
Nejsou zde žádné nedosažitelné stavy.
Úplně definovaný DKA:
ε-uz | a | b | c | |||||
---|---|---|---|---|---|---|---|---|
→I | {1} | {1, 2, 3, 6, 7, 8, 9, 10, 12} | {4, 11} | II | ∅ | T | {13} | III |
II | {4, 11} | {4, 10, 11, 12} | {11} | IV | {5} | V | {13} | III |
III→ | {13} | {13} | ∅ | T | ∅ | T | ∅ | T |
IV | {11} | {10, 11, 12} | {11} | IV | ∅ | T | {13} | III |
V | {5} | {2, 3, 5, 6, 7, 8, 9, 10, 12} | {4, 11} | II | ∅ | T | {13} | III |
T | {T} | T |
Minimalizace:
≡0 | a | b | c | ||||
---|---|---|---|---|---|---|---|
A→ | III→ | T | B | T | B | T | B |
→B | →I | II | B | T | B | III | A |
V | II | T | III | ||||
II | IV | V | III | ||||
IV | IV | T | III | ||||
T | T | B | T | B | T | B |
≡1 | a | b | c | ||||
---|---|---|---|---|---|---|---|
A→ | III→ | T | T | T | T | T | T |
→B | →I | II | B | T | C | III | A |
V | II | T | III | ||||
IV | IV | T | III | ||||
II | IV | B | V | B | III | A | |
T | T | T | T | T | T | T | T |
≡2 | a | b | c | ||||
---|---|---|---|---|---|---|---|
A→ | III→ | T | T | T | T | T | T |
→B | →I | II | C | T | T | III | A |
V | II | T | III | ||||
IV | IV | B | T | T | III | A | |
C | II | IV | B | V | B | III | A |
T | T | T | T | T | T | T | T |
≡3 | a | b | c | ||||
---|---|---|---|---|---|---|---|
A→ | III→ | T | T | T | T | T | T |
→B | →I | II | C | T | T | III | A |
V | II | T | III | ||||
C | II | IV | D | V | B | III | A |
D | IV | IV | D | T | T | III | A |
T | T | T | T | T | T | T | T |
≡3 = ≡4 = ≡
Převeďte automat M2 na redukovaný deterministický konečný automat M2′ přijímající komplement jazyka (nad abecedou {a, b, c}) popsaného výrazem r2.
Uvažte NKA M3 nad abecedou Σ = {a, b} z obrázku 1:
Řešením rovnic nad regulárními výrazy sestavte k tomuto automatu ekvivalentní regulární výraz.
Stavy jsem si označil X, Y, Z ve směru z leva.
Nechť M1 = {Q, Σ, δ, q0, F} je nedeterministický konečný automat. Mějme funkci Φ: Σ* → (Σ ∪ {•})*, kde • ∉ Σ, definovanou následujícím předpisem
Například: Φ(aa) = aa•, Φ(abcde) = ab•cd•e
Navrhněte a formálně popište algoritmus, který má na vstupu automat M1, a jehož výstupem bude (nedet.) konečný automat M2 takový, že L(M2) = {Φ(w) | w ∈ L(M1)}.
Vstup: NKA M1 = (Q, Σ, δ, q0, F)
Výstup: NKA M2 = (Q′, Σ′, δ′, q0′, F′)
Mějme jazyk L = {w | w ∈ {a, b, c}* ∧ #a(w) = #b(w) ∧ #c(w) = 1}, kde #x(w) je počet symbolů x ve slově w. Je jazyk L regulární? Dokažte nebo vyvraťte.
Předpokládejme, že L je regulární. Pak musí platit: ∃p > 0: ∀w ∈ L: |w| ≥ p ⇒ ∃x, y, z ∈ Σ*: w = xyz ∧ 0 < |y| ≤ p ∧ ∀i ≥ 0: xyiz ∈ L.
Uvažujme slova w ve tvaru apcbp. |w| ≥ p. Pak lze při i ≠ 1 zvolit y následujícími způsoby:
Nelze tedy najít takové rozdělení xyz, které by uspokojilo podmínky pumping lemmatu, jazyk tedy není regulární.
Uvažujme algebru regulárních množin (ARM) nad abecedou Σ.
Ukažte, že pro ARM platí následující vztah: A*A* = A*, kde A je libovolná regulární množina. Nepoužívejte fakt, že ARM je Kleeneho algebrou.
Určete, zdali je ⊆ totální uspořádání v ARM. Tedy že pro libovolné dvě regulární množiny A a B platí vždy alespoň jedna z nerovností A ⊆ B nebo B ⊆ A. Své tvrzení dokažte.
Uvažme regulární množiny A = {a} a B = {b}. Neplatí pro ně ani jedna z nerovností A ⊆ B nebo B ⊆ A, ⊆ tedy není totální uspořádání v ARM.