Ábécé (informatika)
 |
Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye. |
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
