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

Visszavontam Szikszaizoli (vita) szerkesztését (oldid: 14808054) tévedés
(Nem uniója, hanem halmaza.)
(Visszavontam Szikszaizoli (vita) szerkesztését (oldid: 14808054) tévedés)
Készítsünk <math>A</math> elemeiből véges sorozatokat minden lehetséges módon. Jelölje <math>A^{1}</math> az egyelemű sorozatok halmazát (ezekből értelemszerűen annyi van, ahány jelből áll az ábécé), <math>A^{2}</math> a kételeműekét, és így tovább. <math>A^{0}</math> jelenti az üres sorozatok halmazát (ez megint csak könnyen beláthatóan egyelemű). A hatványjelölés a halmaz önmagával vett [[Descartes-szorzat]]aira utal.
 
Jelölje <math>A^* = \left\{A^{0}, \cup A^{1}, \cup A^{2}, \dotscup \right\}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.
 
Észrevehető, hogy a definíció megengedi az ''üres szót'' is (ami nem más, mint egy nulla hosszúságú jelsorozat), és gyakran az <math>e</math>, <math>\epsilon</math> vagy a <math>\Lambda</math> [[szimbólum]]okkal jelölik. Bár véges halmaz az ábécé, és a belőlük képzett jelsorozatok ([[ábécé (informatika)|szavak]]) hossza is véges (bár nem korlátos), egy nyelvhez mégis akár megszámlálhatóan végtelenül sok jelsorozat is tartozhat (mivel a szavak száma nincs korlátozva, akár a teljes univerzumot is vehetjük!). A formális nyelvek száma kontinuum számosságú (mivel az univerzum hatványhalmazát képezve megkapjuk az összes formális nyelv halmazát; és nyilván az univerzum megszámlálhatóan végtelen számosságú, mivel elemei felsorolhatóak).