Abeceda (formální jazyky) - Alphabet (formal languages)

Ve formální teorii jazyka je abeceda neprázdnou sadou symbolů / glyfů , o které se obvykle uvažuje jako o reprezentaci písmen, znaků nebo číslic, ale mimo jiné by „symboly“ mohla být také sada fonémů (zvukových jednotek). Abecedy v tomto technickém smyslu množiny se používají v nejrůznějších oborech včetně logiky, matematiky, informatiky a lingvistiky. Abeceda může mít jakoukoli mohutnost („velikost“) a v závislosti na jejím účelu může být konečná (např. Abeceda písmen „a“ až „z“), spočetná (např. ) Nebo dokonce nespočetná (např. ). ${\ displaystyle \ {v_ {1}, v_ {2}, \ ldots \}}$${\ displaystyle \ {v_ {x}: x \ v \ mathbb {R} \}}$

Řetězce , také známé jako „slova“, nad abecedou jsou definovány jako posloupnost symbolů ze sady. Například abeceda malých písmen „a“ až „z“ lze použít k vytvoření anglických slov jako „ledovec“, zatímco abeceda velkých i malých písmen lze také použít k vytvoření vlastních jmen, například „Wikipedia“. Běžná abeceda je {0,1}, binární abeceda a „00101111“ je příklad binárního řetězce . Rovněž lze uvažovat o nekonečné posloupnosti symbolů.

Z praktických důvodů je často nutné omezit symboly v abecedě tak, aby byly při interpretaci jednoznačné. Pokud je například dvoučlenná abeceda {00,0}, řetězec napsaný na papír jako „000“ je nejednoznačný, protože není jasné, zda se jedná o posloupnost tří symbolů „0“, za „00“ následuje „0“ nebo „0“ následovaný „00“.

Zápis

Pokud L je formální jazyk, tedy (možná nekonečná) množina konečných délka řetězce je abeceda L je množina všech symbolů, které se mohou vyskytnout v každém řetězci v L . Například pokud L je množina všech identifikátorů proměnných v programovacím jazyce C , abeceda L je množina {a, b, c, ..., x, y, z, A, B, C, .. ., X, Y, Z, 0, 1, 2, ..., 7, 8, 9, _}.

Vzhledem k abecedě je sada všech řetězců délky nad abecedou označena . Sada všech konečných řetězců (bez ohledu na jejich délku) je označena hvězdným operátorem Kleene jako , a také se nazývá Kleeneho uzavření . Zápis označuje množinu všech nekonečných posloupností v abecedě a označuje množinu všech konečných nebo nekonečných posloupností. ${\ displaystyle \ Sigma}$${\ displaystyle n}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma ^ {n}}$${\ textstyle \ bigcup _ {i \ in \ mathbb {N}} \ Sigma ^ {i}}$${\ displaystyle \ Sigma ^ {*}}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma ^ {\ omega}}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma ^ {\ infty}}$${\ displaystyle \ Sigma ^ {\ ast} \ pohár \ Sigma ^ {\ omega}}$

Například pomocí binární abecedy {0,1} jsou řetězce ε, 0, 1, 00, 01, 10, 11, 000 atd. V Kleeneově uzávěru abecedy (kde ε představuje prázdný řetězec ). .

Aplikace

Abecedy jsou důležité při používání formálních jazyků , automatů a poloautomatů . Ve většině případů je pro definování instancí automatů, jako jsou deterministické konečné automaty (DFA), nutné určit abecedu, ze které jsou vytvořeny vstupní řetězce pro automat. V těchto aplikacích je abeceda obvykle požadována jako konečná množina , ale není jinak omezena.

Při použití automatů, regulárních výrazů nebo formálních gramatik jako součásti algoritmů zpracování řetězců lze za abecedu považovat znakovou sadu textu, který má být těmito algoritmy zpracován, nebo podmnožinu povolených znaků ze znakové sady.

Viz také

• Kombinatorika slov

Reference

Literatura

• John E. Hopcroft a Jeffrey D. Ullman, Úvod do teorie automatů, jazyků a výpočtů , Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN   0-201-02988-X .