Úkol 1

Bc. Jan Kaláb <xkalab00@stud.fit.vutbr.cz>

Příklad 1

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 = {

S → aXbY

X → aXb | ε

Y → bbY | ε

}

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.

Příklad 2

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.

Strom RV:
Strom RV

RKA:
RKA

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

Úplně definovaný DKA

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 = ≡

Redukovaný DKA 1) Sink stav je pro přehlednost vynechán

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.

Redukovaný DKA přijímající komplement jazyka

Příklad 3

Uvažte NKA M3 nad abecedou Σ = {a, b} z obrázku 1:
Obrázek 1: NKA M3
Ř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.

X = aY + aZ

Y = aY + bZ + ε

Z = bX

X = aY + abX = abX + aY

Y = aY + bbX + ε

X = (ab)*aY

Y = a*(bbX + ε)

X = (ab)*a(a*(bbX + ε))

X = (ab)*aa*(bbX + ε)

X = (ab)*a+(bbX + ε)

X = (ab)*a+bbX + (ab)*a+

X = ((ab)*a+bb)*(ab)*a+

X = (ab + a+bb)*a+

Příklad 4

Nechť M1 = {Q, Σ, δ, q0, F} je nedeterministický konečný automat. Mějme funkci Φ: Σ* → (Σ ∪ {•})*, kde • ∉ Σ, definovanou následujícím předpisem

Φ(ε) = ε

Φ(a1) = a1, kde a1 ∈ Σ

Φ(a1a2u) = a1a2 • Φ(u), kde a1, a2 ∈ Σ, u ∈ Σ*

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′)

Q′ = {(q0, n) | q0 ∈ Q; n ∈ {0, 1, 2}}

Σ′ = Σ ∪ {•}

q0′ = (q0, 0)

F′ = {(q, n) | q ∈ F; n ∈ {0, 1}}

δ′ = ∀a ∈ Σ; ∀q1, q2 ∈ Q:

δ(q1, a) = q2 →

δ′((q1, 0), a) = {(q2, 1)} ∪ δ′((q1, 0)

δ′((q1, 1), a) = {(q2, 2)} ∪ δ′((q1, 1)

δ′((q1, 2), •) = {(q1, 0)} ∪ δ′((q1, 2), •)

Příklad 5

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:

aa…aacbb…bb: #a(w) ≠ #b(w)

aa…aacbb…bb: #a(w) ≠ #b(w)

c ∈ y: #c(w) ≠ 1

Nelze tedy najít takové rozdělení xyz, které by uspokojilo podmínky pumping lemmatu, jazyk tedy není regulární.

Příklad 6

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.

Ukážeme, že A*A* ⊆ A*

Ukážeme, že ∀w ∈ A*A*: w ∈ A*

Uvažme livobolné w ∈ A*A*

Dle definice ., w = w1 . w2 pro w1 ∈ A* a w2 ∈ A*

Dle definice *, w1 = w1¹ . w2¹ . … . wn¹ pro n ≥ 0, wi¹ ∈ A pro 1 ≤ i ≤ n a podobně w2 = w1² . w2² . … . wm² pro m ≥ 0, wi² ∈ A pro 1 ≤ i ≤ m

Z definic . a *, w1¹ . … . wn¹ . w1² . … . wm² ∈ A*

Ukážeme, že A* ⊆ A*A*

Ukážeme, že ∀w ∈ A*: w ∈ A*A*

Uvažme livobolné w ∈ A*

Víme, že ε ∈ A*

w . ε ∈ A*A* dle definice . jazyků ∧ w . ε = w z definice . řetězců a tedy w ∈ A*A*

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.