„Formális nyelv” változatai közötti eltérés

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 (például [[karakter]] [[string]]ek, jelsorozatok) [[halmaz]]a, amelyekkel a ''formális nyelvek elmélete'' foglalkozik. (Más kontextusban, mint például jog vagy politika, a ''formális nyelv'' kifejezés alatt egy, a napi beszédtől eltérő, udvarias, megfontolt, körülíró jellegű, túlzottan modoros kifejezési módot értenek. Jelen cikkben 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.)

 

Jelölje <math>A^* = A^{0} \cup A^{1} \cup A^{2} \cup \dots</math> az ábécé elemeiből képzett véges sorozatok halmazát (ezt az <math>A</math> ábécé feletti '''univerzumnak''' hívjuk). Ekkor '''formális nyelvnek''' nevezzük <math>A^{*}\, </math> egy (nem feltétlenül valódi) [[Halmaz#Részhalmaz|részhalmazát]]. Szokásos még az <math>A\, </math> '''ábécé feletti formális nyelv''' megnevezés is.

 

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ául <math>L_1</math>, <math>L_2</math>, <math>L_a</math>, stb.)

 

Legyen az ábécé <math>A=\left \{ a , b \right \}</math>. Ekkor egy jelsorozat például <math>ababba</math>.

Egy egyszerű nyelv lehet a fenti ábécé alapján például az, amely az összes olyan jelsorozatot tartalmaza, amelyekre igaz, hogy ugyanannyi <math>a</math> szimbólumból és <math>b</math> szimólumból állnak.

* egy bizonyos [[Turing-gép]]et megállító bemeneti jelek halmaza.

 

Egy formális nyelv nagyon sok lehetséges módon meghatározható, többek között:

 

* 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]].

 

Adott formális nyelvből vagy nyelvekből műveletekkel új nyelvek állíthatóak elő. Tegyük fel, hogy <math>L_{1}</math> és <math>L_{2}</math> közös ábécén értelmezett nyelvek. A formális nyelvek halmazok, tehát a halmazműveletek minden további nélkül alkalmazhatóak rájuk:

* metszet – <math>L_1 \cap L_2</math> – ''közösrész képzés'' művelet az <math>L_{1}</math> és <math>L_{2}</math> nyelvre előállítja az összes olyan jelsorozatot, amelyek <math>L_1</math>-ben és <math>L_{2}</math>-ben is léteznek.

* unió – <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 formális nyelvek speciális halmazok, így speciális műveletek is értelmezhetőek rajtuk:

* konkatenáció – <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.

* 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 formális nyelvekkel kapcsolatosan gyakran felmerülő kérdés '''„milyen nehéz eldönteni egy adott szóról, hogy egy adott nyelvhez tartozik-e?”'''

 

További fontos, generatív nyelvekkel kapcsolatos problémák:

== Források ==

 

* Csirmaz, László: ''Matematikai logika egyetemi jegyzet'', ELTE Bp., 1994 ([http://www.renyi.hu/~csirmaz/ Postscript változat])

* Szeredi - Lukácsy - Benkő: A szemantikus világháló elmélete és gyakorlata. Typotex Kiadó, 2005. ISBN 963-9548-48-0

[[en:Formal language]]

[[ar:لغة شكلية]]

[[bs:Formalni jezik]]

[[cs:Formální jazyk]]