Digszám 02 Környezetfüggetlen nyelvek

Question 1

Mi az a környezetfüggetlen nyelvtan (CFG)?

Answer 1

Egy formális nyelvtan, ahol minden szabály bal oldalán egyetlen nemterminális áll, amit egy tetszőleges szimbólumláncra lehet cserélni – függetlenül a környezetétől.

Question 2

Mi a CFG négy komponense?

Answer 2

• $V$: nemterminális szimbólumok* $\Sigma$: terminális szimbólumok (ábécé)* $R$: szabályok (pl. $A → aB$)* $S$: kezdőszimbólum

Question 3

Mit jelent, hogy egy szó generálható a CFG-ből?

Answer 3

Azt, hogy a kezdőszimbólumból ($S$) szabályalkalmazások sorozatával el tudunk jutni a szóhoz:$$S ⇒^* w$$

Question 4

Mi az a veremautomata (PDA)?

Answer 4

Egy olyan automata, ami egy veremmel kiegészítve képes felismerni környezetfüggetlen nyelveket – ezáltal bonyolultabb szerkezeteket is kezelhet, mint a véges automaták.

Question 5

Mi a PDA formális definíciója?

Answer 5

$$M = (K, \Sigma, \Gamma, \delta, s, F)$$* Állapotok ($K$),* Bemeneti ábécé ($\Sigma$),* Veremábécé ($\Gamma$),* Átmenetfüggvény ($\delta$),* Kezdőállapot ($s$),* Elfogadó állapotok ($F$)

Question 6

Mit tartalmaz egy PDA-konfiguráció?

Answer 6

Egy aktuális állapot, a hátralévő bemenet és a verem tartalma:$(q, w, \gamma)$

Question 7

Hogyan ismer fel egy PDA olyan szavakat, mint $a^n b^n$?

Answer 7

Minden beolvasott ‘a’-nál jelet tesz a verembe, majd minden ‘b’-nél kivesz. Ha végére elfogy a bemenet és a verem is, a szó elfogadott.

Question 8

Milyen műveletekre zártak a környezetfüggetlen nyelvek?

Answer 8

• Unió
• Konkatenáció
• Kleene-csillag

Question 9

Milyen műveletekre nem zártak a környezetfüggetlen nyelvek?

Answer 9

• Komplementer
• Metszet (kivéve: CFG ∩ reguláris → CFG)

Question 10

Mi az a Kleene-csillag CFG esetén?

Answer 10

Egy nyelv szavainak tetszőleges számú egymás utáni ismétlése, beleértve az üres szót is.

Question 11

Mi a különbség a CFG és a PDA között?

Answer 11

• A CFG generálja a szavakat (levezetés szabályokkal)* A PDA felismeri a szavakat (input + verem feldolgozás alapján)