5. gyakorlat

Feladat (regex / 8.)

Adjon meg reguláris kifejezést a következő azonosítókhoz! (Betűk alatt az angol > ábécé kis- és nagybetűit, számjegyek alatt a decimális számjegyeket értjük.)

• Betűvel kezdődik, számjeggyel, betűvel vagy _ jellel folytatódik
• Szigorítás: az utolsó karakter nem lehet _
• További szigorítás: nem lehet egymás mellett két _

1. \([a-z A-Z] ([a-z A-Z 0-9 "_"])+\)
2. \([a-z A-Z] (([a-z A-Z 0-9 "_"])* [a-z A-Z 0-9])?\)
3. \([a-z A-Z] ("_"? [a-z A-Z 0-9])+\)

Véges determinisztikus automaták

• Karika: állapot
• Duplán meghúzott karika: elfogadó állapot (csak itt terminálhat az automata)

Determinisztikus mert egy állapotból a másik állapotokba egyértelműen tudunk eljutni, tehát nem mutat nyíl ugyanazzal a betűvel többfelé.

Feladat (Automaták / 1.)

Mely alábbi szavakat fogadják el az alábbi véges determinisztikus automaták?

\(\varepsilon\), a, b, aa, ab, ba, aaa, aab, aba, abb, baa, aaaa, abab

\(L = \{u \in \{a, b\}^* \mid \ell(u) = 3k + 1, \, (k \in \N) \}\)

1. a, b, aaaa, abab

1. (b betűvel kezdődőeket biztos nem fogja elfogadni)
   • ab, aab, abb, abab

Feladat (Automaták / 4.)

a?

a+

_[0-9]

(a|b|c)d*