„Formális nyelv” változatai közötti eltérés
| [nem ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a Bot: következő hozzáadása: sh:Formalni jezik |
a Bot: pl. javítása példáulra, Replaced: pl. → például (4) |
||
1. sor:
A '''formális nyelv''' a [[matematika]], a [[matematikai logika|logika]] és a [[informatika]] számára egy véges [[ábécé (informatika)|ábécéből]] generálható, véges hosszúságú szavak (
==Definíció==
9. sor:
Kitüntetett nyelvek az univerzum, a csak az üres jelsorozatot tartalmazó nyelv, és az egyetlen jelsorozatot sem tartalmazó nyelv.
Az egyes nyelveket szokás <math>L</math> betűvel jelölni, és ha többet is használunk, indexszel megkülönböztetni őket (
==Példák==
43. sor:
* A ''right quotient'' – <math>L_{1}/L_{2}</math> – ''különbségképzés'' művelet az <math>L_{1}</math> és <math>L_{2}</math> nyelvek között előállítja az összes olyan <math>L_{2}</math>-ben létező <math>w</math> jelsorozatot, amely jelsorozatok az <math>L_{1}</math> nyelvben <math>vw</math> formában fordulnak elő (ahol <math>v</math> jelsorozat az <math>L_{1}</math> nyelvben létezik).
* A ''tranzitív lezárt'' (lezárt, lezárás, angolul ''[[Kleene star]]'', Kleene csillag) – <math>L_{1}^{*}</math> – a tranzitív lezárt 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 '''mindig''' része a <math>L_{1}^{*}</math> nyelvnek, minden <math>L_{1}</math> nyelvre! (Ha az eredeti nyelv nem is tartalmazta az üres jelsorozatot, a tranzitív lezártja akkor is tartalmazni fogja!) A legalább egy betűt (karaktert) tartalmazó nyelvek tranzitív lezártja végtelen számosságú; az elnevezés onnan származik, hogy a tranzitív lezárt az összes az olyan elemet tartalmazza, ami az eredeti nyelv szavaiból kiindulva konkatenációk tetszőleges egymás után alkalmazásával megkapható (lezárt, mert ez a "legnagyobb" ilyen halmaz, elemeinek konkatenációjával már nem bővíthető).
* 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 (
* A ''shuffle'', ''megkever'' művelet az <math>L_{1}</math> és az <math>L_{2}</math> nyelvek között előállítja az összes <math>v_{1}w_{1}v_{2}w_{2}...v_{n}w_{n}</math> formában leírható jelsorozatot, ahol <math>n \ge 1</math> és a <math>v_{1},...,v_{n}</math> jelsorozatok, amelyek az <math>L_{1}</math> nyelvben léteznek, és az előzőek szerinti értelemben össze vannak kapcsolva a <math>w_{1},...,w_{n}</math> jelsorozatokkal, amelyek az <math>L_{2}</math> nyelvben léteznek.
== A generatív nyelvek ==
A formális nyelvek definíciója (hogy minden formális nyelv egy univerzum részhalmaza) nyilván általános, de praktikus értelemben használhatatlan definíció (hiszen
Ezt, és a generatív nyelvek Chomsky-féle osztályozását részletesen lásd a [[formális nyelvtan]] szócikket!!
| |||