Kihagyás

2. gyakorlat

1.14. Feladat

Döntsük el, hogy az alábbi nyelvek végesek vagy végtelenek! A végteleneket kezdjük el felsorolni lexikografikusan!
\(\varnothing\) véges
\(\{\varepsilon\}\) véges
\(\{a^nb^n \; \| \; n \geq 0\}\) \(\{\varepsilon, ab, aabb, aaabbb, \dots\}\)
\(\{a^nb^n \; \| \; n \geq 0\}\) \(\{\varepsilon, ab, aabb, aaabbb, \dots\}\)
\(\{a\}^*\{b\}^*\) \(\{\varepsilon, a, b, aa, ab, bb\}\) (véges)
\(\{ a^n b^k \;\) | \(\; n \geq 0\), \(k \geq 0\}\) \(\{\varepsilon, a, b, aa, ab, bb, aaa, aab, abb, bbb, \ldots\}\)
\(\{ u\in\{a,b\}^*\| u=u^{-1} \}\) (palindrom szavak) \(\{\varepsilon, a, b, aa, bb, aaa, aba, bab, bbb, \ldots\}\)
\(\{ uu^{-1} \| u\in\{a,b\}^* \}\) TODO

Nyelvtanok (grammatikák)

Definíció: Grammatikának (nyelvtannak) a következő négyest nevezzük:

\(G = (N,T,P,S)\)

  • \(N\): a nemterminális ábécé
  • \(T\): a terminálisok ábécéje
  • \(P\): átirányítási szabályok véges halmaza
  • \(S\): a kezdőszimbólum

Példa

| - OR (ejtsd: csík)

S: start szimbólum

(\(\Rightarrow\)) = levezetési lépés jelőlése

The goal: Eljutni egy olyan állapotba hogy csak kisbetűk legyenek, nagybetűk bad because yes.

S -> aA -> ac

S => aA => abA => abbA => abbc

Ami megegyezik: \(L(G)=\{a\}\{b\}^*\{c\}=\{ab^nc|n \geq 0\}\)

"Látunk szabály bal oldalán betűt és átírjuk másik betűre a szabály jobb oldala alapján"

  • Logika 101

1. feladat

  1. Mely szavak vezethetők le az alábbi nyelvtanokból? (A kezdőszimbólumot S jelöli.)

1. feladat / a

\[\begin{align*} S &\to aA \\ A &\to c | bA \\ \end{align*}\]

Ez már volt!

1. feladat / b

\[ S \to \varepsilon | aaSb \]

\(S \Rightarrow aaSb \Rightarrow aaaaSbb \Rightarrow \cdots \Rightarrow aaaaaaaaaabbbbb\)

\(\varepsilon, aab, aaaabb, ...\) = \(\{a^{2n}b^n\;|\; n \geq 0\}\)

1. feladat / c

\[\begin{align*} S &\to YSb \\ S &\to V \\ YV &\to Vaa \\ YV &\to aaa \\ \end{align*}\]

\(S \Rightarrow \green{YSb} \Rightarrow Y\green{YSb}b \Rightarrow YY\green{V}bb \Rightarrow Y\green{Vaa}bb \Rightarrow \green{aaa}aabb\)

(Zöld: az újonnan beírt rész)

\(\{a^{2n+1}b^n \; | \; n \geq 1\}\)

n-szer alkalmazzuk az első szabályt: \(Y^nVb^n\)

3. szabályt ismételjük, ameddig csak egy \(YV\) marad. (tehát n-1 alkalommal). Ez minden iterációkor 2 \(aa\)-t add hozzá

alkalmazzuk a 4. szabályt (ez a string elejére helyez \(aaa\)-t)

Nyelvek fajtái

  • környezetfüggő
    • A szabály bal oldalán is lehet tetszőleges számű terminális és nemterminális szimbólum
  • környezetfüggetlen
    • A szabály bal oldalán csak EGY nemterminális szimbólum szerepelhet (pl. bötűűű)

1. feladat / c folytatása

megegyező, de környezetfüggetlen

Eredeti (környezetfüggő):

\[\begin{align*} S &\to YSb \\ S &\to V \\ YV &\to Vaa \\ YV &\to aaa \\ \end{align*}\]

Átalakított (környezetfüggetlen):

\[\begin{align*} S &\to aaaVb \\ V &\to aaVb \\ V &\to \varepsilon \end{align*}\]

\(S \Rightarrow aaaVb \Rightarrow aaaaaVbb \Rightarrow aaaaabb\)

2. feladat

Készítsünk nyelvtant, mely azokat az \(u \in \{a, b\}^*\) szavakat fogadja el, melyek a-val kezdődnek és b-vel végződnek!

\[\begin{align*} S &\to aBb \\ B &\to a \mid b \mid BB \mid \varepsilon \end{align*}\]

\(S \Rightarrow aBb \Rightarrow ?\)

3. feladat

Készítsünk nyelvtant a 4-gyel osztható bináris számok nyelvéhez!

4 binárisan: \(100\)

Példák: \(0 = 0\), \(100 = 4\), \(1000 = 8\), \(1100 = 12\), \(10000 = 16\)

\[\begin{align*} S &\to 0 \mid 1A \\ A &\to 0A \mid 00 \mid 1A \end{align*}\]

\(0: S \Rightarrow 0 \Rightarrow 1B \Rightarrow 100\)

\(100: S\) etc

4. feladat

Készítsünk nyelvtant, mely \(\{a^n b^n \mid n \geq 1\}\) szavait fogadja el!

\[\begin{align*} S &\to aBb \mid ab \\ B &\to aBb \mid \varepsilon \mid ab \end{align*}\]
\[\begin{align*} S &\to aSb \mid ab \\ \end{align*}\]

Hárommal osztható számok, for shits and giggles

\[\begin{align*} S &\to A \mid B \mid C \\ A &\to 0A \mid 1B \mid 2C \mid 3A \mid 4B \mid 5C \mid 6A \mid 7B \mid 8C \mid 9A \mid \varepsilon \\ B &\to 0B \mid 1C \mid 2A \mid 3B \mid 4C \mid 5A \mid 6B \mid 7C \mid 8A \mid 9B \\ C &\to 0C \mid 1A \mid 2B \mid 3C \mid 4A \mid 5B \mid 6C \mid 7A \mid 8B \mid 9C \\ \end{align*}\]

Szorgalmi házi

5. feladat

ZH plusz pont

\(\varepsilon, ab, ba, aabb, \dots\)

Egy megoldás: \(S \to \varepsilon \mid aSbS \mid bSaS\)