Matematické Fórum

Rony · 25. 01. 2010 17:26

Zdravím, chtěl bych Vás poprosit o radu...mám tady zadání gramatiky a automatu a potřeboval bych to vyřešit i s nějakým laickým postupem, jak jste k tomu prišli, jelikož tomu vůbec nerozumím...diky moc

Kondr · 25. 01. 2010 20:26

Sbírka odkazů na různé materiály je zde: http://www.fi.muni.cz/usr/kretinsky/fja1.html
Já jsem se formály a automaty učil z toho prvního PDF (Křetínský, Černá, Kučera), možná ti bude milejší něco jiného.

K jedničce: napíšeme si pár slov, které gramatika generuje a z nich snadno nahlédneme, že lze jazyk popsat regulárním výrazem, jde o regulární jazyk.

Ke dvojce: stav s2 je peklo, když se do něj dostaneme, už se nevyhrabeme. Vyhovující slovo musí proto začínat nulou, následovat musí samé jedničky (na počtu nezáleží). Slova samých jedniček vyrábí neterminál X daný předpisem
$X\to \lambda$
$X\to 1X$
neterminál popisující celý jazyk je proto
$S\to 0X$ .