Számelm1 IGAZ/HAMIS

Minden L nyelvre L * \ {ε} = L+

Hamis

Legyen V tetszőleges ábécé és L1, L2, L3 ⊆ V*. Ekkor (L1 ∪ L2)L3 = L1L3 ∪ L2L3.

Igaz

Az (ab)** és az (ab) * reguláris kifejezések ugyanazt a nyelvet írják le.

Igaz

Minden lineáris grammatika által generált nyelv leírható reguláris kifejezéssel.

Hamis

Minden reguláris kifejezéssel leírható nyelv felismerhető veremautomatával.

Igaz

G = ({S,X}, {c, d}, {S → cXS, S → ε, XS → Xdd, d → cS, X → cc}, S) egy 0-típusú grammatika.

Hamis (nem érvényes grammatika d → cS szabály miatt)

Legyen G = (N, T, P, S) tetszőleges környezetfüggetlen grammatika. Ha S → ε ∈ P, akkor S nem szerepel G egyetlen szabályának jobboldalán se.

Hamis

Ha a G = (N, T, P, S) grammatika minden egyes szabályának alakja A → aB, A → a, vagy A → ε (A,B ∈ N, a ∈ T), akkor G 3-as normálformájú.

Hamis (A -> a miatt)

Legyen A = (Q, T, δ,Q0, F) tetszőleges nemdeterminisztikus véges automata. Ekkor megadható olyan A′ veremautomata, amelyre N(A′) = L(A) teljesül.

Igaz

Az {uu^(−1) | u ∈ {a, b, c}*, |u| ≤ 100} nyelv reguláris.

Igaz

Tegyük fel, hogy egy A = (Q, {a, b}, δ, q0, F) véges determinisztikus automatában az r /∈ F állapotra δ(r, a) = q és δ(r, b) = r. Ekkor L(A, r) = {a}L(A, q) ∪ {b}L(A, r).

Igaz

A környezetfüggetlen grammatikák inaktív nemterminálisaiból nem vezethető le terminális szó.

Igaz

Ha az A = (Q, T, δ, q0, F) véges determinisztikus automata minden q, q′ ∈ Q állapotaira q′ elérhető q-ból, akkor A összefüggő. Következmény: L2 nem zárt a metszetre, komplementerre, különbségre, szimmetrikus differenciára

Igaz

A környezetfüggetlen nyelvek osztálya zárt a komplemens műveletre nézve.

Hamis

Legyen A = (Z, Q, T, δ, z0, q0, F) tetszőleges veremautomata. Ekkor L(A) 1-es típusú nyelv.

Igaz

Legyen A = (Z, Q, T, δ, z0, q0, F) egy veremautomata. Legyen (xy, r) ∈ δ(z, q, ε); ekkor ezen átmenet alkalmazása után kapott konfigurációban a verem kettővel több betűt fog tartalmazni, mint az azt megelőző konfigurációban (x, y, z ∈ Z, q, r ∈ Q).

Hamis

Legyen A = (Z, Q, T, δ, z0, q0, F) tetszőleges veremautomata. Ekkor megadható olyan G 3-as normálformájú grammatika, amelyre L(G) = L(A) teljesül.

Hamis

Legyen G = (N, T, P, S) egy tetszőleges környezetfüggetlen grammatika. Ekkor az L(G)-beli szavak levezetési fáiban minden csúcsnak 0, 1 vagy 2 gyereke van.

Hamis

A Kis Bar-Hillel Lemma segítségével nyelveknek a reguláris nyelvek osztályába való tartozását lehet igazolni.

Hamis

A környezetfüggő grammatikák hossznemcsökkentő grammatikák is egyben.

Igaz

Minden L nyelvre L3 = {uuu | u ∈ L}.

Hamis

Minden L nyelvre L* \ L+ = {ε}.

Hamis

Legyen V egy ábécé és L1, L2 ⊆ V* tetszőleges V feletti nyelvek. Ekkor L1 ∩L2 = komplementer(L1 ∪ L2).

Hamis

A véges nemdeterminisztikus automaták által felismert nyelvek leírhatóak reguláris kifejezéssel.

Igaz

Az (ε + ab + cd) és az (ab + cd) reguláris kifejezések ugyanazt a nyelvet írják le.

Igaz

Legyen A = (Q, T, δ,Q0, F) tetszőleges véges nemdeterminisztikus automata. Ekkor megadhatóolyan G Chomsky normálformájú grammatika, melyre L(G) = L(A) teljesül.

Igaz

A G = ({S,A}, {c, d}, {S → cA, S → ε, A → dA, A → c }, S) grammatika 3-as

normálformájú.

Hamis (A → c miatt)

Legyen E → ε a G grammatika egy szabálya, ahol E NEM a G kezdőszimbóluma. Ekkor a G grammatika biztosan nem 1-típusú.

Igaz

Ha a G = (N, T, P, S) grammatika minden egyes szabályának alakja A → BC, A → a alakú (A,B,C ∈ N, a ∈ T), akkor G Chomsky normálformájú.

Igaz

Bármely két reguláris kifejezéssel leírható nyelv metszete is leírható reguláris kifejezéssel.

Igaz

Az {a^nc^n | n ≥ 1} nyelv környezetfüggetlen.

Igaz

A 2-típusú grammatikák aktív nemterminálisai elérhetők.

Hamis

Ha C ∈ N a G = (N, T, P, S) környezetfüggetlen grammatika elérhető nemterminálisa, akkor G-nek legalább egy olyan szabálya van, amelynek a jobboldala egyetlen C-ből áll.

Hamis

Ha az A = (Q, T, δ, q0, F) véges determinisztikus automata minden állapota elérhető q0-ból, akkor A összefüggő.

Igaz

A 3-típusú szóprobléma polinom időben eldönthető.

Igaz

Legyen A = (Z, Q, T, δ, z0, q0, F) tetszőleges veremautomata. Ekkor L(A) generálható Kuroda normálformájú grammatikával.

Igaz

Legyen A = (Z, Q, T, δ, z0, q0, F) egy veremautomata. Ha minden z ∈ Z, q ∈ Q, a ∈ T ∪ {ε} esetén |δ(z, q, a)| = 1, akkor a veremautomata determinisztikus.

Igaz

Legyen A = (Z, Q, T, δ, z0, q0, F) tetszőleges veremautomata. Ekkor megadható olyan A′ = (Z′,Q′, T, δ′, z′0 , q′0 , F′) veremautomata, amelyre N(A′) = L(A) teljesül.

Igaz

Legyen G = (N, T, P, S) egy Chomsky normálformájú grammatika. Ekkor az L(G)-beli szavak levezetési fáiban a leveleknek nincs testvére.

Igaz

Legyen L = {cb, cbac, bca, bb}. Ekkor Lε = ∅.

Hamis ??

ab az abbaba szó egyik suffixe.

Hamis

Minden L ⊆ {a, b}* nyelvre L{ε} = L.

Igaz

Minden lineáris grammatikával generálható nyelv leírható reguláris kifejezéssel.

Hamis

A cc* reguláris kifejezés a {c^(2n) | n ≥ 0} nyelvet írja le.

Hamis

Minden reguláris kifejezéssel leírható nyelv generálható 3-as normálformájú grammatikával.

Igaz

Legyen A = (Q,Σ, δ,Q0, F) tetszőleges nemdeterminisztikus véges automata. Ekkor megadható olyan R reguláris kifejezés, amelyre L(R) = L(A) teljesül.

Igaz

A G = ({S,X}, {c, d}, {S → cX, S → ε, X → ddX, X → cd}, S) grammatika 3-típusú.

Hamis (X → ddX)

Legyen G = (N,Σ, P, S) tetszőleges hossznemcsökkentő grammatika. Ha u → v ∈ P és u ̸= S, akkor |v| ≥ 1.

Igaz

Ha a G = (N,Σ, P, S) grammatika minden egyes szabályának alakja A → BC, AB → AC, BA → CA, A → a, vagy A → ε (A,B,C ∈ N, a ∈ Σ), akkor G Kuroda normálformájú.

Hamis (A → ε miatt)

Az {u ∈ {a, b}* | a b-k száma u-ban páratlan} nyelv környezetfüggetlen.

Igaz

A 2-típusú szóprobléma polinom időben eldönthető.

Igaz

Ha B ∈ N a G = (N,Σ, P, S) környezetfüggetlen grammatika elérhető nemterminálisa, akkor létezik olyan A ∈ N, hogy A → B ∈ P.

Hamis

Ha az A = (Q,Σ, δ, q0, F) véges determinisztikus automata bármely F-beli állapota q0-ból elérhető, akkor A összefüggő.

Hamis

A reguláris nyelvek osztálya zárt a metszet műveletére nézve.

Igaz

A környezetfüggő nyelvek osztálya zárt az unió műveletére nézve.

Igaz

Legyen A = (Z, Q,Σ, δ, z0, q0, F) tetszőleges veremautomata. Ekkor L(A) 2-típusú nyelv.

Igaz

Legyen A = (Z, Q,Σ, δ, z0, q0, F) egy veremautomata. Legyen (x, r) ∈ δ(z, q, b); ekkor ezen átmenet alkalmazása után kapott konfigurációban a verem eggyel több betűt fog tartalmazni, mint az azt megelőző konfigurációban (x, z ∈ Z, b ∈ Σ, q, r ∈ Q).

Hamis

Legyen A = (Z, Q,Σ, δ, z0, q0, F) tetszőleges veremautomata. Ekkor megadható olyan G Chomsky normálformájú grammatika, amelyre L(G) = L(A) teljesül.

Igaz

Legyen G = (N,Σ, P, S) egy Chomsky normálformájú grammatika. Ekkor az L(G)-beli szavak levezetési fáiban minden csúcsnak 0, 1 vagy 2 gyereke van.

Igaz

A Nagy Bar-Hillel Lemma segítségével nyelveknek a 2-típusú nyelvek osztályába való tartozását lehet igazolni

Hamis

Minden h : V 1 → V 2 homomorfizmus esetén h(ε) = ε.

Igaz

Minden L nyelvre L+ ⊂ L*. (⊂: valódi tartalmazás.)

Hamis

Az üres nyelv (∅) reguláris nyelv.

Igaz

A véges determinisztikus automaták által felismert nyelvek generálhatóak jobblineáris grammatikával.

Igaz

A bc(bc) és a (bc) reguláris kifejezések ugyanazt a nyelvet írják le.

Hamis

Minden A véges nemdeterminisztikus automatához megadható olyan A′ véges determinisztikus automata, amelyre L(A′) = L(A) teljesül.

Igaz

A G = ({S,A}, {c, d}, {S → AcA, S → d, A → cdA, A → cc}, S) grammatika 3-típusú.

Hamis

Legyen S → ε és S → SAB a G = (N, T, P, S) grammatika két szabálya, ahol A,B ∈ N. Ekkor a G grammatika biztosan nem környezetfüggetlen.

Hamis

Ha egy G = (N, T, P, S) grammatika minden egyes szabálya A → vBw vagy A → w alakú, ahol A,B ∈ N, v,w ∈ T*, akkor G lineáris grammatika.

Igaz

Egy reguláris és egy környezetfüggetlen nyelv metszete környezetfüggetlen.

Igaz

L2 zárt a metszet műveletre nézve.

Hamis

Ha egy G környezetfüggetlen grammatika kezdőszimbóluma aktív, akkor L(G) ̸= ∅.

Igaz

A környezetfüggetlen grammatikák környezetfüggő grammatikák is egyúttal.

Igaz

Ha az A = (Q, T, δ, q0, F) véges determinisztikus automata q és r állapotai megkülönböztethetetlenek (q ∼ r), továbbá r ∈ F is teljesül, akkor q ∈ F.

Igaz

Legyen G = (N, T, P, S) egy 2-típusú grammatika és u = t1 · · · tn ∈ T+ (n ≥ 1) egy szó. u?∈L(G) eldöntéséhez Cocke, Younger és Kasami algoritmusa j − i szerinti növekvő sorrendben kiszámítja a Hij halmazokat (1 ≤ i ≤ j ≤ n). Ekkor u ∈ L(G) ⇐⇒ H1n ̸= ∅.

Hamis (az számít, hogy a kezdőszimbólumot tartalmazza)

Legyen A = (Z, Q, T, δ, z0, q0, F) tetszőleges veremautomata. Ekkor L(A) generálható 3-as normálformájú grammatikával.

Hamis

Legyen A = (Z, Q, T, δ, z0, q0, F) egy determinisztikus veremautomata. Ekkor bármely z ∈ Z, q ∈ Q, a ∈ T ∪ {ε} esetén |δ(z, q, a)| = 1.

Hamis (0 lépés is lehet)

Legyen A egy tetszőleges veremautomata. Ekkor megadható egy olyan A′ determinisztikus veremautomata, amelyre L(A′) = L(A) teljesül.

Hamis

Bármely G környezetfüggetlen grammatika bármely levezetési fájában minden olyan csúcs, ami nem levél, G egy nemterminálisával van címkézve.

Igaz

Legyen L = {a, ab, bab}. Ekkor |La| = 1.

Hamis (La: a-val kezdődő szavak halmaza)

Minden h homomorfizmusra h(ε) = ε.

Igaz

Az (ab) és az a b * reguláris kifejezések ugyanazt a nyelvet írják le.

Hamis

Legyen V tetszőleges ábécé és L ⊆ V* tetszőleges nyelv. Ekkor L3 = {uuu | u ∈ L}.

Hamis

|{aa, aaa}^2| = 4.

Hamis

Minden 2-típusú nyelv leírható reguláris kifejezéssel.

Hamis

Minden jobblineáris grammatika egyben lineáris grammatika is.

Igaz

Ha a G = (N,Σ, P, S) grammatika 3-as normálformájú, akkor minden egyes szabályának alakja A → aB (A,B ∈ N, a ∈ Σ) vagy A → a (A ∈ N, a ∈ Σ).

Hamis

Ha a G = (N,Σ, P, S) grammatika minden egyes szabályának alakja A → aB (A,B ∈ N, a ∈ Σ) vagy A → a (A ∈ N, a ∈ Σ), akkor G 3-as normálformájú.

Hamis

Legyen A = (Q,Σ, δ,Q0, F) tetszőleges nemdeterminisztikus véges automata. Ekkor megadható olyan A′ determinisztikus véges automata, amelyre L(A′) = L(A) teljesül.

Igaz

Ha L-nek véges sok páronként különböző maradéknyelve van, akkor reguláris.

Igaz

Tegyük fel, hogy egy A = (Q, {a, b}, δ, q0, F) determinisztikus véges automatában az r ∈ Q \ F állapotra δ(r, a) = r és δ(r, b) = s. Ekkor L(A, r) = {a}L(A, r) ∪ {b}L(A, s).

Igaz

A 2-típusú grammatikák elérhető nemterminálisai aktívak.

Hamis

Minden Chomsky normálformájú grammatika környezetfüggő grammatika is egyben.

Igaz

Bármely környezetfüggő grammatika 0-típusú nyelvet generál.

Igaz

Legyen A = (Z, Q,Σ, δ, z0, q0, F) tetszőleges veremautomata. Ekkor N(A) 1-típusú nyelv.

Igaz

Legyen A = (Z, Q,Σ, δ, z0, q0, F) egy veremautomata. Ekkor a (z, q) ∈ δ(z, q, ε) átmenet szerinti egyenlépéses redukció hatására a verem eggyel több betűt fog tartalmazni, mint előtte (z ∈ Z, q ∈ Q).

Hamis

Legyen A = (Z, Q,Σ, δ, z0, q0, F) tetszőleges veremautomata. Ekkor megadható olyan A′ determinisztikus veremautomata, amelyre L(A′) = L(A) teljesül.

Hamis

Legyen G = (N,Σ, P, S) egy tetszőleges környezetfüggetlen grammatika. Ha egy levezetési fában egy 2-gyerekes, A címkéjű csúcsnak a baloldali gyereke B, a jobboldali C, akkor az A → BC szabály P-beli.

Igaz (?)

Minden hossznemcsökkentő grammatika Kuroda normálformájú is egyben.

Hamis

Létezik olyan h homomorfizmus, melyre h(u) = ε. és u ̸= ε.

Igaz