No Title

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.