Automaty, gramatiky

30.12.2017

Zkuste napsat gramatiku (nebo automat), který bude generovat nějaký nekonečný jazyk, který Vám přijde zajímavý. Automat nebo gramatiku vložte do souboru a stručně popište, co dělá. Pokud si nebudete vědět rady tak se můžete podívat do Skript v rozšiřujících materiálech nebo se mne zeptat. 

Komentáře:

Dobrý večer, snažila jsem se vytvořit nějakou neomezenou gramatiku. Jestli to chápu správně, každý jazyk typu nula je nekonečný. Proto jsem u jazyka zvolila hodnoty na n-tou, aby to bylo nekonečné. Pak jsem se snažila vymyšlené slovo vygenerovat ze svých pravidel přepisu a podařilo se. Akorát si nejsem jistá, jestli když přepisuju nějaké písmeno (například W na X), tak jestli toto pravidlo přepisu můžu použít v celém tom přepisování jen jednou nebo i vícekrát. Nevím, jestli je to z mého komentáře pochopitelné... Když tak bych se Vás asi doptala ve středu.

Tak už jsem na to přišla. To, co jsem vytvořila, může generovat nekonečný jazyk, akorát jsem uvedla špatně příklad. Nekonečný jazyk můžu vytvořit přepisováním W - wW - wwW - wwwW atd. Nebo můžu W přepsat jinak - W - wW - wxX - wxxX - wxxxX atd. Stejně to funguje i u Y - yY nebo u Z - zZ.

M. Č.: Dobrý den, díky moc. Je to jak píšete. Jen pozor - správně Váše gramatika generuje (pokud se správně dívám) jazyk w^m x^n y^k z^l. Jinými slovy - nijak nezajišťujete, že od každého písmene tam bude stejný počet, což by to společné na n implikovalo.