Regulární jazyk: Porovnání verzí
Smazaný obsah Přidaný obsah
m Bot: Odstranění 20 odkazů interwiki, které jsou nyní dostupné na Wikidatech (d:q752532) |
Dal jsem definici regulárních jazyků nahoru. To, že regulární jazyk je rozpoznatelný konečným automatem, je dost komplikovaná věta a asi není vhodné to jen tak říkat hned na úvodu. |
||
Řádek 1:
'''Regulární jazyky''' jsou jakési nejjednodušší [[formální jazyk|formální jazyky]]. Regulární jazyky nad abecedou Σ lze zavést následujícím způsobem:
* prázdný jazyk Ø je regulární.▼
*
O regulárních jazycích lze dokázat řadu tvrzení. Např. formální jazyk je regulární, právě když:
* je akceptovaný nějakým deterministickým [[konečný automat|konečným automatem]],
* je akceptovaný nějakým nedeterministickým [[konečný automat|konečným automatem]],
Řádek 7 ⟶ 14:
* může být vygenerován [[regulární gramatika|regulární gramatikou]]
▲* prázdný jazyk Ø je regulární.
▲* pro každé ''a'' ∈ Σ, jazyk { ''a'' } je regulární.
▲* Pokud ''A'' a ''B'' jsou regulární jazyky, jsou ''A'' U ''B'', ''A'' • ''B'', a ''A''* regulární.
▲* žádné další jazyky nad Σ nejsou regulární.
Všechny [[konečný jazyk|konečné jazyky]] jsou regulární. Dalším příkladem je například jazyk nad abecedou {''a'', ''b''} obsahující lichý počet symbolů ''a''.
| |||