Kihagyás

4. gyakorlat

Készítsünk nyelvtant ahhoz az a, b betűk feletti nyelvhez, melynek szavai ugyanannyi a-t és b-t tartalmaznak!

Bizonyítás:

\(L = \{u \in \{a, b\}^* \mid \ell_a(u)=\ell_b(u)\}\)

\[\begin{align*} S &\to \varepsilon \\ S &\to aSbS \\ S &\to bSaS \end{align*}\]

Bizonyítandó: \(L\) nyelv szabályainak megfelel \(\iff\) a nyelvtannak megfelel

  • a nyelvtannak megfelel \(\Rightarrow\) \(L\) nyelv szabályainak megfelel

Mivel a nyelvtan minden szabályában megegyező számú \(a\) és \(b\) jön létre, ezért e két karakter száma mindig megegyezik

  • \(L\) nyelv szabályainak megfelel \(\Rightarrow\) a nyelvtannak megfelel

Teljes indukció

\(\ell_u=2k\)

  • \(k=0\): triv.
  • \(k=1\):
    • \(ab\): \(S \Rightarrow aSbS \xRightarrow{*} ab\)
    • \(ba\): \(S \Rightarrow bSaS \xRightarrow{*} ba\)

Indukció

  • tegyük fel, hogy le tudjuk vezetni a legfeljebb \(2k\) hosszú szavakat
  • lássuk be, hogy a \(2(k+1)\) hosszú szót is le tudjuk vezetni
    • Ha u szó a-val kezdődik, akkor
      • lesz egy b párja is
      • tehát \(u=vw\), ahol \(v=axb\), ahol \(v, w\) és \(x\) szavak
      • Azt is tudjuk, hogy \(\ell_a(v)=\ell_b(v)\)
      • tehát \(u=axbw\)
      • \(S \Rightarrow aSbS \xRightarrow{\text{mivel x-ről és w-ről is tudjuk az indukciós feltevés szerint, hogy felírható a nyelvtanunkkal}} axbw\)

Feladat: nyelvtanok / 8.

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

\(S \to aAbBc\)

\(A \to \varepsilon \mid aAb \mid Ab\)

\(B \to \varepsilon \mid bBc \mid Bc\)

\[\begin{align*} S &\to aSBc \mid V \\ cB &\to Bc \\ VB &\to bV \\ Vc &\to c \end{align*}\]

\(S \Rightarrow aSBc \Rightarrow aaSBcBc \Rightarrow aaVBcBc \Rightarrow aaVBBcc \Rightarrow aabVBcc \Rightarrow aabbVcc \Rightarrow aabbcc\)

Regex

Regex101

Mi a retek az a regex?

Regex: Regular expression (reguláris kifejezés)

Illeszkednek bizonyos szavakra, szócsoportokat lehet vele megadni szabályok alapján.

  • |: vagy
  • [a-z]: betűk a-tól z-ig (csak kisbetűk!)
  • [0-9]: egész számok 1-től 9-ig
  • +: \(1 \leq\) db az előző tokenből
  • *: \(0 \leq\) db az előző tokenből
  • ?: 0 vagy 1 az előző tokenből
  • ^: negálás

Feladat: Regex / 1.

Mely szavakra illeszkednek az alábbi regexek?

A szavak: \(\varepsilon\), a, b, aa, ab, ba, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaaaa, bbbbb, ababab, babab

Retek Szavak
"" \(\varepsilon\)
a a
ab ab
a\|b a, b
a* \(\varepsilon\), a, aa, aaa (legalább 0 db a-ból áll)
a\|b* \(\varepsilon\), a, b, bbb, bbbbb
ab* a, ab, abb
a*b b, ab, aab
a*b* \(\varepsilon\), a, b, aa, ab, aaa, aab, abb, bbb, aaaaaa, bbbbb
a*\|b \(\varepsilon\), a, b, aa, aaa, aaaaaa
a*\|b* \(\varepsilon\), a, b, aa, aaa, bbb, aaaaaa, bbbbb
(ab)* \(\varepsilon\), ab, ababab

Feladat: regex / 2.

Mely szavakra illeszkedik az a? reguláris kifejezés? Írjuk fel a standard műveletek segítségével!

a?: \(\varepsilon, a\) = ""|a

Feladat: regex / 3.

Mely szavakra illeszkedik az a+ reguláris kifejezés? Írjuk fel a standard műveletek segítségével!

a+ = aa*

a, aa, aaa, aaaa, aaaaa, aaaaaa, aaaaaaa, aaaaaaaa, aaaaaaaaa

Feladat: regex / 4.

Mely szavakra illeszkedik az [a-d] reguláris kifejezés? Írjuk fel a standard műveletek segítségével!

[a-d] = a|b|c|d

a, b, c, d

Feladat: regex / 5.

Mely szavakra illeszkedik az [^a-z] reguláris kifejezés? Kezdjük el felírni a standard műveletek segítségével!

Negálás

[^a-z]: 0, 1, 2, \(\ldots\), z, !, ., 👍, 💺, 🎉, 😷, 😍, 😬, 😛, 👏, 👏, 😪, 😴, 🤦, 🐈, ǎ

😊

Feladat: regex / 6.

Adjon meg reguláris kifejezést a következő számformátumokhoz!

  1. Decimális egész szám (legalább egy számjegy 0-9-ig)
  2. Olyan decimáis egész szám, amely több számjegy esetén nem kezdődhet nullával
  3. Előjeles decimális egész szám (opcionális + vagy – az elején)
  4. Decimális törtszám (tizedespont előtt legalább egy számjegy)
  1. [0-9]+
  2. [1-9][0-9]*|0
  3. ("+"|"-")?([1-9][0-9]*|0)

  4. [0-9]+"."[0-9]+

  5. |: vagy

  6. [a-z]: betűk a-tól z-ig (csak kisbetűk!)
  7. [0-9]: egész számok 1-től 9-ig
  8. +: \(1 \leq\) db az előző tokenből
  9. *: \(0 \leq\) db az előző tokenből
  10. ?: 0 vagy 1 az előző tokenből
  11. ^: negál

HF: +0.5 a rendes számábrázolás. Egész szám végén ne legyen pont és a leading 0-k - 0 jó - 0. nem jó - 00 nem jó - 0.05 jó - 0.100 legyen jójó etc...

([0-9]+"."[0-9]+) | (([1-9][0-9]*|0)(^"."))

Feladat: regex / 7.

Készítsen reguláris kifejezést a helyes hh:mm óraformátum ellenőrzésére, ahol a hh a 00..23, míg az mm a 00..59 értékeket veheti fel!$ ((0 \mid 1) [0-9] \mid 2[0-3])$ ":" \([0-5][0-9]\)

(0|1|2[0-3]):[0-5][0-9]

Óra ((0|1)|2[0-3]):[0-5][0-9]