Epsilon és Regex

\(\varepsilon\) mentesítés

Tétel

Minden \(G=(N,T,P,S)\) környezetfüggetlen (2-es típusú) grammatikához konstruálható egy vele ekvivalens \(G'=(N',T,P',S')\) környzetfüggetlen grammatika úgy, hogy nincs benne \(A\to \varepsilon\) alakú

kivéve, ha \(\varepsilon \in L(G)\), akkor \(S'\to\varepsilon\in P2'\), de ekkor \(S'\) nem szerepel egyik szabály jobb oldalán sem

Remember KES

E-szám mentes példa

Like my grandma likes her salad...

\[ H:=\{A\in N\,|\,A\underset{G}{\Rightarrow}^*\varepsilon\} \]

\(i\ge1;\; H_i:\)

\(H_1:=\{A\in N\,|\,\exists A\to \varepsilon \in P\}\)

\(H_{i+1}:=H_i\cup\{A\in N\,|\,\exists A\to w \in P,\;w\in H_i^*\}\)

\(H_1\subseteq H_2\subseteq\ldots\subseteq H_i\)

Ha \(a\in N\,\land\,A\underset{G}{\Rightarrow}^*\varepsilon\quad\iff\quad A\in H\)

E-szám mentes példa 2

\[ L=\{u\in \{a,b\}^*\;|\;\ell_a(u)=\ell_b(u)\ge 0\} \]

\(G = (\{S\},\{a,b\},P,S)\)

\[ \begin{array}{lcl} P: & S\to & aSbS \\ & S\to & bSaS \\ & S\to & \varepsilon \end{array} \]

\(G' = (\{S',\;S\},\{a,b\},P',S')\)

\[ \begin{array}{lcl} P': & S\to & aSbS \\ & S\to & abS \\ & S\to & aSb\\ & S\to & ab \end{array} \]

\[ L(G)=L(G') \]

Nyelvosztályok zártsága reguláris műveletekre

Tétel

\(\mathcal{L_i},\;i=0,1,2,3\) nyelvosztályok mindegyike zárt a reguális műveletekre

Legyen \(\varphi\) \(n\)-változós nyelvi művelet
- Tehát ha \(L_1,\ldots,L_n\) nyelvek, akkor \(\varphi(L_1,\ldots,L_n)\) is nyelvek
\(\mathcal{L}\) TODO

Unió

\(G=(N,T,P,S)\) az \(L\) nyelv grammatikája
hasonlóan \(G'=(N',T,P',S')\) az \(L'\) nyelv grammatikája
- \(N\cap N'=\emptyset\), illetve \(G,\;G'\) azonos típusúak
\(i=0,2,3\) esetén legyen \(S_0\) új szimbólum
- \(S_0\not\in(N\cup N')\)

\[ G_u=(N\cup N' \cup \{S_0\},T,P\cup P'\cup \{S_0\to S,S_0\t oS'\},S_0) \]

Látható, hogy \(G_u\) típusa megegyezik \(G,\;G'\) típusával

Illetve \(L(G)\cup L(G') = L(G_u)\)

Hope you noticed, i=1 nincs benne

Ekkor nem teljesülne a KES

Megoldás: vegyük \(L_1=L\setminus\{\varepsilon\}\) és \(L_2=L'\setminus\{\varepsilon\}\) nyelveket, makd az uniót követően vezessünk be új kezdőszimbólumot: \(S_1\to\varepsilon,\;S_1\to S_0\) módszer megjavítja a dolgot 👍

Konkatenáció

\(i=3\)

\(P\) szabályhalmazából konstruálunk egy olyan \(P_1\)-et, hogy minden \(A\to u\) alakú szabály helyére \(A\to uS'\) szabályt teszünk

a többi szabályt nem bántjuk

A \(G_c=(N\cup N', T',P_1 \cup P', S)\) grammatika így hármas típusú, és előállítja az \(L(G)L(G')\) nyelvet

Lezárás

\(i=3\)

Legyen \(S_0\) új szimbólum
- \(S_0\not\in N\)
Legyen \(P_1\) új szabályrendszer
- \(A\to u\) helyére \(A\to uS_0\)
\(G_*=(N\cup\{S_0\},\,T,\,P_1\cup P\cup \{S_0\to\varepsilon,\;S_0\to S\},\,S_0)\)
- Sikeresen előállítja az \(L^*\) nyelvet

Hármas nyelvcsalád leírásai

Egy hármas nyelv megadható:

3-as típusú grammatikával
Reguláris kifejezéssel
Véges determinisztikus automatával
Véges nemdeterminisztikus automatával

Igaz, hogy

\[ \mathcal{L}_3=\mathcal{L}_{reg}=\mathcal{L}_{da}=\mathcal{L}_{nda} \]

Reguláris nyelvek

Elemi nyelvek
- \(\emptyset,\{\varepsilon\},\{a\},\quad a\in U\)
- Tehát \(a\) egy tetszőleges betű
Azon nyelvek, amik az elemi nyelvek uniójával, konkatenációjával és lezárásával megadható
Nem létezik más reguláris nyelv \(\large{!}\)

Regulásis gramamtika - Tétel

Minden reguláris nyelvhez adható 3-as típusú grammatika

Az elemi nyelveknek adható

A reguláris műveleteket úgy definiáltuk, hogy 3-as típusú marad a gramamtika

\(G(\{S\},\{a\},\{S\to aS\},S)\quad L(G)=\emptyset\)

\(G(\{S\},\{a\},\{S\to \varepsilon\},S)\quad L(G)=\{\varepsilon\}\)

\(G(\{S\},\{a\},\{S\to a\},S)\quad L(G)=\{a\}\)

Reguláris kifejezések

Take a look at kooootlin's gyak