Какой язык у этих детерминированных конечных автоматов?

Question

Дано:

Понятия не имею, что такое принятый язык.

Глядя на это, вы можете получить несколько конечных результатов:

1.) bb
2.) ab(a,b)
3.) bbab(a, b)
4.) bbaaa

Answer 1

Как написать регулярное выражение для DFA

В любом автомате назначение состояния подобно элементу памяти. Состояние хранит некоторую информацию в автоматическом режиме, например, переключатель вентилятора ON-OFF.
Детерминированные конечные автоматы (DFA), называемые конечные автоматы, потому что конечный объем памяти присутствует в форме состояний. Для любого обычного языка (RL) DFA всегда возможен.

Посмотрим, какая информация хранится в DFA (см. Мой красочный рисунок).
( примечание: в моем объяснении любое число означает ноль или более раз, а Λ является нулевым символом )

---

Состояние-1: - это состояние СТАРТ, и в нем хранится информация , четное число a . И НОЛЬ b.
Регулярное выражение (RE) для этого состояния: = (aa)*.

Состояние-4: Пришло нечетное число a. И НОЛЬ b.
Регулярное выражение для этого состояния: = (aa)*a.

Рисунок: a СИНИЙ состояния = ДАЖЕ число a и КРАСНЫЙ состояний = ODD число a пришло.

УВЕДОМЛЕНИЕ: После первого b движение не может вернуться в состояние 1 и состояние 4.

Состояние-5: идет после Yellow b. Yellow b означает b after odd numbers of a.
Как только вы получаете b после нечетных чисел a (в состоянии-5), все становится приемлемым, потому что есть собственный цикл для (b, a) в состоянии- 5.

Вы можете написать для состояния-5: Желтый-b, сопровождаемый любой строкой a, b, которая является = Yellow-b (a + b)*

Состояние-6: Просто чтобы различить, нечетное a или четное.

Состояние-2: идет после четного a, затем b, затем любое число b. = (aa)* bb*

Состояние-3: идет после состояния-2, затем сначала a, затем происходит цикл через состояние-6. Мы можем написать для состояния-3 приходит = state-2 a (aa)* = (aa)*bb* a (aa)*

Поскольку в нашем DFA у нас есть три конечных состояния, поэтому язык, принятый DFA, представляет собой объединение (+ в RE) трех RL (или трех RE).
Таким образом, язык, принятый DFA, соответствует трем принимающим состояниям-2,3,5 , и мы можем написать так:

 State-2 +  state-3           + state-5    

(aa)*bb* + (aa)*bb* a (aa)* + Yellow-b (a + b)*

Я забыл объяснить how Yellow-b comes?
ОТВЕТ: Yellow-b является b после состояния-4 или состояния-3. И мы можем написать как:

Yellow-b = ( state-4 + state-3 ) b = ((aa)*a + (aa)*bb* a (aa)*) b

[ ОТВЕТ ]
(aa)*bb* + (aa)*bb* a (aa)* + ((aa)*a + (aa)*bb* a (aa)*) b (a + b)*

---

Английский Описание языка : DFA допускает объединение трех языков

• ДАЖЕ НОМЕРОВ a, СЛЕДУЮЩИХ ОДНЫМ ИЛИ БОЛЕЕ b,
• ДАЖЕ НОМЕРОВ a, СЛЕДУЮЩИХ ОДНЫМ ИЛИ БОЛЬШЕ b, С НЕСКОЛЬКИМИ НОМЕРАМИ a ' s.
• СТРОКА ПРЕФИКСА a И b С ЧИСЛОМ НЕТРАДА a, СЛЕДУЕТ ПО b , сопровождаемый ЛЮБОЙ СТРОКОЙ a И b И Λ.

Английский Описание сложное, но это единственный способ описать язык. Вы можете улучшить его, сначала преобразовав данный DFA в минимизированный DFA, а затем напишите RE и описание.

---

Также существует производный метод для нахождения RE из заданного графа переходов с использованием Терм Ардена Я объяснил здесь Как написать регулярное выражение для DFA с использованием теоремы Ардена Граф переходов сначала должен быть преобразован в стандартную форму, в которой нет нулевого хода и единственного начального состояния.Но мне нравится изучать теорию вычислений на основе анализа вместо математического подхода к выводу.

Answer 2

Я думаю, что этот вопрос больше не актуален :) и, вероятно, лучше провести вас через него, чем просто сформулировать ответ, но я думаю, что у меня есть базовое выражение, которое охватывает его (возможно, оно минимизируется), поэтому япросто запишите это для будущих искателей

(aa)*b(b)* // for stoping at 2
U
(aa)*b(b)*a(aa)* // for stoping at 3
U
(aa)*b(b)*a(aa)*b((a)*(b)*)* // for stoping at 5 via 3
U
a(aa)*b((a)*(b)*)* // for stoping at 5 via 4

Answer 3

Приведенные вами примеры (1 - 4): не язык , принятый DFA.Это просто строки, которые принадлежат языку , который принимает DFA.Следовательно, все они относятся к одному и тому же языку.

Если вы хотите выяснить регулярное выражение , определяющее этот DFA, вам нужно будет выполнить то, что называется k-path индукция, и вы можете прочитать об этом здесь .