logo

Примери ДФА

Пример 1:

Дизајн ФА са ∑ = {0, 1} прихвата оне стрингове који почињу са 1 и завршавају се са 0.

прег_матцх

Решење:

ФА ће имати почетно стање к0 из којег ће само ивица са улазом 1 ићи у следеће стање.

Примери детерминистичких коначних аутомата

У стању к1, ако прочитамо 1, бићемо у стању к1, али ако прочитамо 0 у стању к1, доћи ћемо до стања к2 које је коначно стање. У стању к2, ако прочитамо или 0 или 1, прећи ћемо у стање к2 или стање к1, респективно. Имајте на уму да ако се унос заврши са 0, биће у коначном стању.

Пример 2:

Дизајнирајте ФА са ∑ = {0, 1} прихвата једини улаз 101.

Решење:

Примери детерминистичких коначних аутомата

У датом решењу видимо да ће бити прихваћен само унос 101. Дакле, за улаз 101, не постоји друга путања приказана за други улаз.

Пример 3:

Дизајн ФА са ∑ = {0, 1} прихвата паран број 0 и паран број 1.

Решење:

схилпа схетти

Овај ФА ће размотрити четири различите фазе за улаз 0 и улаз 1. Фазе могу бити:

Примери детерминистичких коначних аутомата

Овде је к0 почетно и коначно стање. Пажљиво приметите да се одржава симетрија 0 и 1. Сваком стању можемо да повежемо значења као:

к0: стање парног броја 0 и парног броја 1.
к1: стање непарног броја 0 и парног броја 1.
к2: стање непарног броја 0 и непарног броја 1.
к3: стање парног броја 0 и непарног броја 1.

Пример 4:

Дизајн ФА са ∑ = {0, 1} прихвата скуп свих стрингова са три узастопне нуле.

Решење:

Низови који ће бити генерисани за ове конкретне језике су 000, 0001, 1000, 10001, .... у којима се 0 увек појављује у групи од 3. Графикон прелаза је следећи:

ц код низ стрингова
Примери детерминистичких коначних аутомата

Имајте на уму да се редослед троструких нула одржава да би се дошло до коначног стања.

Пример 5:

Дизајнирајте ДФА Л(М) = {в | в ε {0, 1}*} и В је низ који не садржи узастопне јединице.

Решење:

Када се појаве три узастопна 1, ДФА ће бити:

Примери детерминистичких коначних аутомата

Овде су две узастопне 1 или једна 1 прихватљиве, дакле

Примери детерминистичких коначних аутомата

Фазе к0, к1, к2 су коначна стања. ДФА ће генерисати низове који не садрже узастопне 1 као што су 10, 110, 101,..... итд.

Пример 6:

Дизајнирајте ФА са ∑ = {0, 1} прихвата низове са парним бројем 0 праћених појединачним 1.

Решење:

ДФА се може приказати прелазним дијаграмом као:

Примери детерминистичких коначних аутомата