„Szerkesztő:Beginner 25/Munka1” változatai közötti eltérés
Tartalom törölve Tartalom hozzáadva
244. sor:
{{Lektor}}
'''Formális nyelv''' a [[matematika]], a [[logika]] és a [[
A következőkben a formális nyelvet a formális nyelvek elmélete szerinti értjük, és minden esetben szigorúan csak írott nyelvről beszélünk, ezért a jelsorozat elemei megjeleníthető, nyomtatható karakterek.
Legyen egy
Egy tipikus nyelv lehet a fenti
Az '''üres szó''' (ami nem más, mint egy nulla hosszúságú jelsorozat) megengedett és gyakran az <math>e</math>, <math>\epsilon</math> vagy a <math>\Lambda</math> jelöli. Bár véges halmaz az
Néhány példa formális nyelvekre:
268. sor:
* Azon kérdések halmazából, amelyekre IGEN/NEM válsz adható, azok a kérdések, amelyekre IGEN a válasz — lásd [[döntési probléma]].
Néhány művelettel új nyelv állítható elő adott nyelvből vagy nyelvekből. Tegyük fel, hogy <math>L_{1}</math> és <math>L_{2}</math> közös
* A ''concatenation'' — <math>L_{1}L_{2}</math> — ''konkatenáció'' vagy ''összekapcsolás'' művelet előllítja az összes <math>vw</math> formájú jelsorozatot, ahol <math>v</math> egy <math>L_{1}</math>-ből származó jelsorozat, és <math>w</math> a <math>L_{2}</math>-ből származó jelsorozat.
274. sor:
* A ''union'' — <math>L_1 \cup L_2</math> — ''egyesítés'' művelet az <math>L_{1}</math> és <math>L_{2}</math> nyelvre előállítja az összes olyan jelsorozatot, amelyek vagy <math>L_{1}</math>-ben vagy <math>L_{2}</math>-ben léteznek.
* A ''complement'', ''komplementer képzés'' vagy ''kiegészítő képzés'' művelet az <math>L_{1}</math> nyelvre előállítja az összes olyan jelsorozatot, amelyek az <math>L_{1}</math> nyelvben nem léteznek.
*
* A ''[[Kleene star]]'' — <math>L_{1}^{*}</math> — a [[Kleene csillag]] művelet előállítja az összes <math>w_{1}w_{2}...w_{n}</math> formában leírható jelsorozatot, ahol a <math>w_{i}</math> jelsorozat az <math>L_{1}</math> nyelvben létezik és <math>n \ge 0</math>). Meg kell jegyezni, hogy az <math>n = 0</math> értékadás megengedett, tehát az <math>\epsilon</math> üres jelsorozat része az <math>L_{1}</math> nyelvnek.
* A ''reverse'' — <math>L_{1}^{R}</math> — ''fordítottja'' művelet előállítja az összes <math>L_{1}</math> nyelvben létező jelsorozat fordítottját ( pl. az <math>ababba</math> jelsorozat fordítottja a <math>abbaba</math> jelsorozat).
| |||