Рубрики

Составные конечные автоматы (FA)

Обязательное условие — Конечные Автоматы (ФА)
Соединение FA является результирующим DFA, сформированным после выполнения операции (∪, ∩, -) на данных DFA D1 и D2.

D1 = (Q1, ∑, δ, q1, F1) and D2 = (Q2, ∑, δ, q2, F2) 

Где,
Q 1 и Q 2 : множество конечных состояний DFA D1 и D2 соответственно.
Input: входной алфавит содержит конечное количество входных символов.
δ: функция перехода (δ: Qx∑-> Q)
q 1 и q 2 : начальное состояние D1 и D2 соответственно.
F 1 и F 2 : набор конечных состояний DFA D1 и D2 соответственно.

Свойства составных конечных автоматов (ФА):

  1. Количество состояний в составном FA (D1XD2) равно m * n, где m — количество состояний в D1, а n — количество состояний D2.
  2. Начальное состояние соединения FA является комбинацией начальных состояний D1 и D2.
  3. Конечное состояние соединения FA зависит от выполняемой операции.

Пример:

D1 = no. of a's divisible by 2
D2 = no. of b's divisible by 3

D1 ({q1, B}, {a, b}, δ, q1, {q1}), 
D1 ({q2, A, C}, {a, b}, δ, q2, {q2}) 

Построить минимальный FA для:

(D1∪D2), 
(D1∩D2), 
(D1-D2),
(D2-D1) 

Объяснение:

DFA D1:

DFA D2:

1. Союз (D1∪D2):
Любая строка w, принадлежащая либо языку D1, либо языку D2, принимается результирующими составными автоматами.
Конечное состояние : если конечное состояние D1 или конечное состояние D2 содержится в любом из состояний составного FA.

2. Пересечение (D1∩D2):
Любая строка w, принадлежащая как языку D1, так и языку D2, принимается результирующими составными автоматами.
Конечное состояние : если и конечное состояние D1, и конечное состояние D2 содержатся в каком-либо из состояний составного FA.

3. Разница (D1 — D2):
Любая строка w, которая принимается D1, а не D2.
Конечное состояние : если конечное состояние D1 и неконечное состояние D2 содержатся в любом из состояний составного FA.

4. Разница (D2 — D1):
Любая строка w, которая принимается D2, а не D1.
Конечное состояние : если конечное состояние D2 и неконечное состояние D1 содержатся в любом из состояний составного FA.

Рекомендуемые посты:

Составные конечные автоматы (FA)

0.00 (0%) 0 votes