„Formális nyelv” változatai közötti eltéré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.

 

 

É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).