Ábécé (informatika)

A formális nyelvek vizsgálatakor ábécé alatt tetszőleges, ám meghatározott jelek halmazát értjük. Az ábécé jellemzően véges halmaz.

Ennek a Σ halmaznak az elemei lehetnek a hagyományos értelemben vett betűk és/vagy számjegyek is, de lehetnek tetszőleges szimbólumok, jelek is. Az így definiált ábécé elemeiből (azaz a Σ halmaz elemeiből) azok egymás után írásával (konkatenációjával) képezhetünk véges hosszúságú jelsorozatokat, amelyet szavaknak nevezünk. A Σ elemeiből képezhető összes szó halmazát Σ*-gal jelöljük, a Σ* részhalmazait pedig formális nyelveknek nevezzük.

Vegyük észre, hogy jóllehet az ábécé, szó, illetve nyelv elnevezések megegyeznek a köznapi értelemben használtakkal, valójában azonban itt jóldefiniált fogalmakról van szó, amelyek bizonyos értelemben a köznapi értelemben használt szavak absztrahálásával keletkeznek. Vegyük észre továbbá, hogy a nyelv definiálásának a célja az, hogy meghatározzuk, hogy az összes lehetséges szó közül, amit adott jelkészlettel képezni tudunk, azaz "le tudunk írni", kiválasszuk azokat a szavakat (azt a részhalmazát Σ*-nak), amelyek az adott nyelven "értelmesek", jelentéssel bírnak.

Példák

• Legyenek Σ elemei az ASCII karakterek. Ekkor Σ* elemei a véges ASCII jelsorozatok, beleértve a teljesen "értelmetlen" karaktersorozatokat is. Ezekből azonban kiválogathatjuk azokat a jelsorozatokat, amelyek egy-egy C++ programnak felelnek meg és ekkor a Σ fölött definiált nyelv az összes szintaktikusan helyes C++ program halmaza.
• Legyenek Σ elemei a magyar ábécé betűi, illetve magyar nyelv által használt írásjelek, beleértve a szóközt is. Ekkor József Attila minden verse megfeleltethető egy-egy szónak a Σ*-ban, és a nyelv maga állhat József Attila összes költeményeiből.

Halmazelméleti vonatkozások

A ábécé és az ábécé elemein definiált konkatenáció mint kétváltozós művelet félcsoportot alkot, hiszen a konkatenáció a definíciójából következően asszociatív művelet.

Kapcsolódó szócikkek

• Formális nyelv
• Formális nyelvtan
• Halmazelmélet

További információk

• Csirmaz László: Matematikai logika egyetemi jegyzet, ELTE Bp., 1994 (Postscript változat)

• Szendrei Ágnes: Diszkrét matematika Logika, algebra, kombinatorika, Polygon Szeged, 1994