7. Tétel

Question 1

Mi a generatív nyelvtan G = (N, Σ, P, S) felépítése?

Answer 1

N: nemterminálisok halmaza, Σ: terminálisok ábécéje, P: szabályhalmaz (produkciók), S: kezdőszimbólum.

Question 2

Sorolja fel a Chomsky-féle nyelvosztályokat!

Answer 2

0-típusú (kifejezés struktúrájú), 1-típusú (környezetfüggő), 2-típusú (környezetfüggetlen), 3-típusú (reguláris vagy jobblineáris).

Question 3

Milyen korlátozások vonatkoznak a 0-típusú (kifejezés struktúrájú) nyelvekre?

Answer 3

Nincsenek korlátozások a szabályhalmazra.

Question 4

Milyen alakúak a szabályok az 1-típusú (környezetfüggő) nyelvekben?

Answer 4

αAβ⟶αδβ alakúak, ahol A∈N, α,β,δ∈(N∪Σ)∗, δ=λ. S⟶λ megengedett, de S nem szerepelhet jobb oldalon.

Question 5

Milyen alakúak a szabályok a 2-típusú (környezetfüggetlen) nyelvekben?

Answer 5

A⟶α alakúak, ahol A∈N és α∈(N∪Σ)+. S⟶λ megengedett, de S nem szerepelhet jobb oldalon.

Question 6

Milyen alakúak a szabályok a 3-típusú (reguláris vagy jobblineáris) nyelvekben?

Answer 6

A⟶aB vagy A⟶a alakúak, ahol A,B∈N és a∈Σ. S⟶λ megengedett, de S nem szerepelhet jobb oldalon.

Question 7

Miért “reguláris” (szabályos) a 3-típusú nyelvtan elnevezése?

Answer 7

Jól kezelhetőségéből adódik, minden szabály jobb oldalán legfeljebb egy nemterminális szimbólum állhat, mégpedig annak is a jobb oldali végén.

Question 8

Mi a véges automata definíciója absztrakt gépként?

Answer 8

Absztrakt gép, amely áll egy vezérlőegységből, egy input szalagból és egy olvasó fejből.

Question 9

Hogyan működik egy véges automata?

Answer 9

Kezdőállapotban van, olvasófej az első szimbólumra mutat. Szimbólumokat olvas, olvasófej jobbra mozog, vezérlőegység állapotot válthat. Ha az utolsó szimbólumot is elolvasta és végállapotban van, akkor elfogadja a szót.

Question 10

Milyen típusú nyelveket ismernek fel a véges automaták?

Answer 10

3-típusú, azaz reguláris nyelveket.

Question 11

Miből áll egy nemdeterminisztikus véges automata (M=(Q,Σ,δ,I,F))?

Answer 11

Q: állapotok halmaza, Σ: input ábécé, δ: átmenetfüggvény, I: kezdőállapotok halmaza, F: végállapotok halmaza.

Question 12

Mi az átmenetfüggvény (δ) a nemdeterminisztikus automatánál?

Answer 12

δ:Q×Σ→P(Q), ahol P(Q) a Q halmaz hatványhalmazát jelöli, azaz több állapotba is átmehet.

Question 13

Mi a véges automata konfigurációja?

Answer 13

Egy (q,w)∈C pár, ahol q az aktuális állapot és w az input szó még el nem olvasott része.

Question 14

Mikor nevezünk egy konfigurációt kezdő konfigurációnak?

Answer 14

Ha q∈I (a kezdőállapotok halmazába tartozik).

Question 15

Mikor nevezünk egy konfigurációt befejező konfigurációnak?

Answer 15

Ha w=λ (az üres szó, azaz az input elfogyott).

Question 16

Mikor elfogadó egy befejező konfiguráció?

Answer 16

Ha q∈F (a végállapotok halmazába tartozik).

Question 17

Mikor elutasító egy befejező konfiguráció?

Answer 17

Ha q∈/F (nem tartozik a végállapotok halmazába).

Question 18

Mi a különbség a determinisztikus és a nemdeterminisztikus véges automata között?

Answer 18

Nemdeterminisztikus: egy input szimbólum hatására több állapotba is átmehet. Determinisztikus: legfeljebb egy állapotba mehet át.

Question 19

Mikor teljesen definiált egy véges automata?

Answer 19

Ha minden q∈Q állapot és minden a∈Σ input szimbólum esetén $$

Question 20

Mikor nevezünk egy L⊆Σ∗ nyelvet automatával felismerhető nyelvnek?

Answer 20

Ha létezik olyan véges automata (M), amelyre L(M)=L.

Question 21

Mikor nevezünk egy L⊆Σ∗ nyelvet reguláris nyelvnek?

Answer 21

Ha automatával felismerhető.

Question 22

Mi a Pumpáló lemma lényege reguláris nyelvekre?

Answer 22

Ha egy nyelv reguláris, akkor létezik egy k szám, hogy minden k-nál hosszabb szó (w) felbontható w1​w2​w3​ alakba úgy, hogy w2​ nem üres, és minden n>0-ra w1​w2n​w3​ is eleme a nyelvnek.

Question 23

Mire használható a Pumpáló lemma?

Answer 23

Annak bizonyítására, hogy egy adott nyelv nem reguláris.