Cseles kérdések:


Igazak-e az alábbi állítások? Az indoklás nem elhanyagolható része a válasznak.

1.

Minden többállapotú PDA-hoz létezik vele egyenértékű egyállapotú PDA.

2.

Egy reguláris nyelv minden részhalmaza reguláris.

3.

Ha az $L_1, \ldots ,L_n$ nyelvek ($n\geq 1$) regulárisak, akkor az ${\cup}_{i=1}^nL_i$ nyelv is reguláris.

4.

Megszámlálhatóan végtelen sok reguláris nyelv uniója nem feltétlenül reguláris

5.

Megszámlálhatóan végtelen sok reguláris nyelv uniója lehet reguláris

6.

Megszámlálhatóan végtelen sok reguláris nyelv van

7.

Attól. hogy L₁ és L₂ nem reguláris, $L_1\cup L_2$ még lehet reguláris

8.

(r^*+s^*)(s^*+r^*)=(r+s)^*

9.

Ha L reguláris, akkor az $L'=\{ww\;\vert\;w\in L\}$ nyelv is reguláris, hiszen L'=L²

10.

Ha L reguláris, akkor L^-1 is reguláris

11.

Ha L egy reguláris nyelv a $\Sigma$ ábécé felett, akkor az $L'=\{w\in{\Sigma}^*\;\vert\;\exists x\in L:\vert x\vert=\vert w\vert\}$ nyelv is reguláris.

12.

Ha M egy PDA, akkor L_u=L_a, ahol L_u azon nyelv, amit az automata üres veremmel elfogad, míg L_a az a nyelv, amit végállapottal elfogad.

13.

Ha L egy CF nyelv és $\epsilon\in L$, akkor van olyan L-t generáló nyelvtan, ami pontosan egy $\epsilon$-szabályt tartalmaz.

Válaszok:

1.

Igaz, mert minden PDA-hoz van CF nyelvtan és minden CF nyelvtanhoz van egy állapotú PDA.

2.

Nem igaz, például ${\{a,b\}}^*$ reguláris, de $\{a^nb^n\;\vert\;n\geq 1\}$ nem az.

3.

Igaz, n-re menő teljes indukcióval be lehet látni.

4.

Igaz, például az $\{a^nb^n\;\vert\;n\geq 1\}$ nyelv előáll a szavaiból egy megszámlálható unióval.

5.

Igaz, ${\{a,b\}}^*$ előáll a szavaiból egy megszámlálható unióval.

6.

Igaz, megbeszéltük év elején.

7.

Igaz, $L_1=\{a^nb^n\;\vert\;n\geq 1\}$, L₂ meg legyen a komplementere.

8.

Nem, például az rsr szó nem eleme a baloldalnak.

9.

Nem, mert egyrészt $L'\not =LL$, másrészt láttuk órán, hogy L' nem reguláris.

10.

Igaz, az L nyelv automatájából lehet automatát csinálni L^-1-hez: minden nyilat megfordítunk, az elfogadók kezdők lesznek, a kezdő meg elfogadó.

11.

Igaz, az L nyelv automatájából lehet automatát csinálni L'-hez: minden létező nyílra ráírunk minden szimbólumot, minden más marad.

12.

Nem igaz, mert nézzük azt az automatát például, ami mindig elfogadó állapotban van és mindent végig is olvas, de sose csinál semmit a veremben, tehát ki se üríti, azaz üres veremmel nem fogad el senkit.

13.

Igaz, a CNF ilyen.