Ábécé (informatika)

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés]

  • 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[szerkesztés]

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[szerkesztés]

További információk[szerkesztés]

  • Csirmaz László: Matematikai logika egyetemi jegyzet, ELTE Bp., 1994 (Postscript változat)
  • Szendrei Ágnes: Diszkrét matematika Logika, algebra, kombinatorika, Polygon Szeged, 1994