приклад 1:
Розробка FA з ∑ = {0, 1} приймає ті рядки, які починаються з 1 і закінчуються на 0.
рішення:
FA матиме початковий стан q0, з якого лише ребро з входом 1 перейде до наступного стану.
У стані q1, якщо ми читаємо 1, ми будемо в стані q1, але якщо ми читаємо 0 у стані q1, ми досягнемо стану q2, який є кінцевим станом. У стані q2, якщо ми читаємо 0 або 1, ми перейдемо відповідно до стану q2 або q1. Зауважте, що якщо вхід закінчується на 0, він буде в кінцевому стані.
приклад 2:
Розробка FA з ∑ = {0, 1} приймає єдиний вхід 101.
рішення:
У наведеному рішенні ми бачимо, що буде прийнято лише введення 101. Отже, для входу 101 немає іншого шляху, показаного для іншого входу.
приклад 3:
Дизайн FA з ∑ = {0, 1} приймає парну кількість 0 і парну кількість одиниць.
рішення:
Цей FA розглядатиме чотири різні етапи для вхідних даних 0 і вхідних даних 1. Етапи можуть бути такими:
Тут q0 є початковим станом і також кінцевим станом. Зверніть увагу, що зберігається симетрія нулів і 1. Ми можемо пов’язати значення з кожним станом як:
q0: стан парної кількості нулів і парної кількості одиниць.
q1: стан непарної кількості 0 і парної кількості 1.
q2: стан непарної кількості нулів і непарної кількості одиниць.
q3: стан парної кількості нулів і непарної кількості одиниць.
Приклад 4:
Дизайн FA з ∑ = {0, 1} приймає набір усіх рядків із трьома послідовними нулями.
рішення:
Рядки, які будуть згенеровані для цієї конкретної мови, це 000, 0001, 1000, 10001, .... у яких 0 завжди з’являється в групі 3. Графік переходів виглядає наступним чином:
Зверніть увагу, що послідовність потрійних нулів підтримується для досягнення кінцевого стану.
Приклад 5:
Створіть DFA L(M) = {w | w ε {0, 1}*} і W — це рядок, який не містить послідовних одиниць.
рішення:
Коли трапляються три одиниці поспіль, DFA буде:
Отже, тут прийнятні дві послідовні 1 або одна 1
Етапи q0, q1, q2 є кінцевими станами. DFA генеруватиме рядки, які не містять послідовних одиниць, наприклад 10, 110, 101 тощо.
Приклад 6:
Розробка FA з ∑ = {0, 1} приймає рядки з парною кількістю 0, за якою йде одна 1.
рішення:
DFA можна показати на діаграмі переходів як:
