Да се построи детерминиран автомат

[counter]

Да се построи минимален , краен , детерминиран автомат , който разпознава точно езика :
[tex]\sum_{}^{ } = {1,4}[/tex]

[tex]L_{1} =a \in \sum_{}^{ } *[/tex] a съдържа като поддума на 114

[nikko]

Ето ти краен и напълно определен ДКА, които разпознава езика.
Остава да се докаже, че е минимален. Това може да стане като се разгледат класовете от думи [tex]\epsilon[/tex], [1], [11], [114]. Очевидно няма как минимален автомат да разпознава езика и да няма различни състояния за тези класове - т.е. минимум четири вътрешни състояния, точно колкото има и този.

[counter]

Мерси , а как разбираме кое число е между 2 състояния , за пример..
ясно е че 1,1,4 e между [tex]q_{0} , q_{1} , q_{2} , q_{3}[/tex] понеже 114 трябва да съществува , но пример от [tex]q_{2}[/tex] излиза 1= и влиза пак в [tex]q_{2}[/tex] 1 неможе ли да е 4 ?

[nikko]

Не, ако е 4, то думи с 114 в тях ще свършват в q_2, а то не е заключително!
Иначе [tex]\delta(q_2,1)=q_2[/tex] за да се разпознават и думи с поддуми от вида [tex]1^k4[/tex] за [tex]k\geq 3.[/tex]