Создайте NFA для следующего языка, определенного над Σ = {0, 1}. D = {0 ^ n 10 ^ m10 ^ q | n, m, q ∈ N, q ≡ nm (mod 5)} - PullRequest
Новая
       5

Создайте NFA для следующего языка, определенного над Σ = {0, 1}. D = {0 ^ n 10 ^ m10 ^ q | n, m, q ∈ N, q ≡ nm (mod 5)}

1 голос
/ 12 февраля 2020

Нужна помощь в решении следующего вопроса:

Создайте NFA для следующего языка, определенного над Σ = {0, 1}.

D = {0 ^ n 10 ^ m10 ^ q | n, m, q ∈ N, q ≡ nm (mod 5)}

Я не понимаю, как создать факторинг NFA в q части языка.

1 Ответ

0 голосов
/ 12 февраля 2020

Мы можем использовать пять состояний, чтобы запомнить значение n mod 5: 

        _______________0______________
       /                              \
       |                              |
       V                              |
----->q0--0-->q1--0-->q2--0-->q3--0-->q4

Теперь нам нужно прочитать 1: 

        _______________0______________
       /                              \
       |                              |
       V                              |
----->q0--0-->q1--0-->q2--0-->q3--0-->q4
       |       |       |       |       |
       1       1       1       1       1
       |       |       |       |       |
       V       V       V       V       V
      q0'     q1'     q2'     q3'     q4'

Теперь мы можем рассмотреть каждый случай индивидуально. Для q0 'мы знаем, что мы видели число 0 в первом разделе, которое совпадает с 0 mod 5. Таким образом, nm = 0 (mod 5) уже известно. Мы можем принять любое число 0, затем 1, а затем принять, если у нас больше нет ввода: мы можем заставить q0 'сделать это: 

     _0_
    /   \
    |   |
    \   /
----->q0'--1-->qA

Для q1' у нас будет q = nm ( mod 5) = m (mod 5), так как n = 1 (mod 5) в этом случае. Мы можем сделать это sh, запомнив текущее значение m (mod 5) и затем найдя столько нулей в q. Таким образом, q1 'может быть заменено на: 

        _______________0________________________
       /                                        \
       |                                        |
       V                                        |
----->q1'--0-->q1''--0-->q1'''--0-->q1''''--0-->q1'''''
       |        |        |          |           |
       1        1        1          1           1
       |        |        |          |           |
       V        V        V          V           V
       qA<--0--qA'<--0--qA''<--0--qA'''<--0--qA''''

qA - это то же самое принимающее состояние, которое мы ввели ранее. Для q2 'мы можем отслеживать текущее значение nm (mod 5), которое составляет 2m (mod 5): 

        _______________0________________________
       /                                        \
       |                                        |
       V                                        |
----->q2'--0-->q2''--0-->q2'''--0-->q2''''--0-->q2'''''
       |        |        |          |           |
       1        1        1          1           1
       |        |        |          |           |
       V        V        V          V           V
       qA      qA''     qA''''     qA'         qA'''

Состояния qA', qA '', qA '' 'и qA '' '' те же, что были введены ранее, но обратите внимание, что порядок теперь другой: это отражает тот факт, что 2 x 0 = 0 (как и прежде), 2 x 1 = 2 (не 1), 2 x 2 = 4 ( не 2), et c.

Мы можем сделать то же самое для q3 'и q4': 

        _______________0________________________
       /                                        \
       |                                        |
       V                                        |
----->q3'--0-->q3''--0-->q3'''--0-->q3''''--0-->q3'''''
       |        |        |          |           |
       1        1        1          1           1
       |        |        |          |           |
       V        V        V          V           V
       qA      qA'''    qA'        qA''''      qA''


        _______________0________________________
       /                                        \
       |                                        |
       V                                        |
----->q4'--0-->q4''--0-->q4'''--0-->q4''''--0-->q4'''''
       |        |        |          |           |
       1        1        1          1           1
       |        |        |          |           |
       V        V        V          V           V
       qA      qA''''   qA'''      qA''        qA'

Объединение всех этих различных DFA в один огромный DFA гарантировано чтобы дать вам DFA, который будет работать. Есть ли существенно похожий NFA, я не могу сказать наверняка. Этот DFA имеет состояния:

  1. q0, q0 ': 2 состояния
  2. q1, q1',…., Q1 '' '' ': 6 состояний
  3. q2, q2 ',…., q2' '' '': 6 состояний
  4. q3, q3 ',…., q3' '' '': 6 состояний
  5. q4, q4 ' ,…., Q4 '' '' ': 6 состояний
  6. qA, qA',…., QA '' '': 5 состояний

Это всего 32 состояния. Если вы хотите попытаться свести к минимуму, вы можете выбить несколько из них.

...