TechCodeview

Пример 1:

Проектирайте NFA за таблицата за преход, както е дадено по-долу:

Решение:

Диаграмата на прехода може да бъде начертана с помощта на функцията за картографиране, както е дадено в таблицата.

Тук,

 δ(q0, 0) = {q0, q1} δ(q0, 1) = {q0, q2} Then, δ(q1, 0) = {q3} Then, δ(q2, 0) = {q2, q3} δ(q2, 1) = {q3} Then, δ(q3, 0) = {q3} δ(q3, 1) = {q3} 

Пример 2:

Проектирайте NFA с ∑ = {0, 1} приема всички низове, завършващи с 01.

Решение:

Следователно NFA ще бъде:

Пример 3:

Проектирайте NFA с ∑ = {0, 1}, в който двойното „1“ е последвано от двойното „0“.

Решение:

FA с двойно 1 е както следва:

безкраен цикъл

Трябва да бъде непосредствено последвано от двойна 0.

Тогава,

Сега преди двойно 1 може да има произволен низ от 0 и 1. По същия начин след двойно 0 може да има произволен низ от 0 и 1.

Следователно NFA става:

Сега разглеждаме низа 01100011

 q0 → q1 → q2 → q3 → q4 → q4 → q4 → q4 

Пример 4:

Проектирайте NFA, в който целият низ съдържа подниз 1110.

Решение:

Езикът се състои от целия низ, съдържащ подниз 1010. Диаграмата на частичен преход може да бъде:

Тъй като 1010 може да бъде поднизът. Следователно ще добавим входните 0 и 1, така че поднизът 1010 на езика да може да се поддържа. Следователно NFA става:

Таблица на прехода за горната диаграма на прехода може да бъде дадена по-долу:

Да разгледаме низ 111010,

 δ(q1, 111010) = δ(q1, 1100) = δ(q1, 100) = δ(q2, 00) 

Заседна! Тъй като няма път от q2 за входен символ 0. Можем да обработим низ 111010 по друг начин.

 δ(q1, 111010) = δ(q2, 1100) = δ(q3, 100) = δ(q4, 00) = δ(q5, 0) = δ(q5, ε) 

Като състояние q5 е състоянието на приемане. Получаваме пълното сканиране и достигаме до крайното състояние.

Пример 5:

Проектирайте NFA с ∑ = {0, 1} приема всички низове, в които третият символ от десния край винаги е 0.

java null проверка

Решение:

Така получаваме третия символ от десния край винаги като '0'. NFA може да бъде:

Изображението по-горе е NFA, защото в състояние q0 с вход 0 можем да отидем или в състояние q0, или в q1.