Докажите, что следующий язык является регулярным: - PullRequest
Новая
       58

Докажите, что следующий язык является регулярным:

0 голосов
/ 03 мая 2019

Пусть L1, L2 - обычные языки.И пусть A1 = 〈Σ, Q, q0, ?1, F1), A2 = 〈Σ, P, p0, ?2, F2) - их DFA.

Докажите, что следующий язык является регулярным, сделавсоответствующий NFA для него:

?3 = {?1?1′?2?2 ′… ???? ′ | ?1?2… ??∈?1, ?1′?2 ′… ?? ′ ∈?2} (имеется в виду язык всех слов, в которых буквына четных позициях (начиная с 0) от L1 и буквы на нечетных позициях от L2.

Буду признателен за помощь. Спасибо.

1 Ответ

1 голос
/ 03 мая 2019

Рассмотрим следующий автомат:

  • алфавит Σ
  • набор состояний (Q x P) объединение (P x Q)
  • начальное состояние (q0,p0)
  • конечные состояния (f1, f2), где f1 и f2 находятся в F1 и F2, соответственно
  • функция перехода, которая переводит (q, p) в (p, q ') символаs, если ?1 переводит q в q 'на s, и который переводит (p, q) в (q, p') символа s, если A2 переводит p в p 'символа s.

Предположимчто у вас есть слово w в L3.Наша машина принимает это?Последовательность ?1, ?2,…, ?n приведет к тому, что первая компонента состояния, в которое поступает автомат, будет такой же, как состояние A1, в которое бы поступило бы, если бы A1 обработал только эту последовательность.Поскольку L3 говорит, что эта последовательность в w является словом в L1, состояние должно было приниматься в A1, поэтому первый компонент находится в F1.Аналогично, последовательность ?1 ', ?2',…, ?n 'является строкой в ​​L2, и поэтому состояние, в которое она приходит, принимает.Таким образом, состояние, достигнутое этим NFA, имеет форму (f1, f2), и, таким образом, строка принимается, как и должно быть.Мы только что утверждали, что NFA принимает по крайней мере строки на этом языке.Остается доказать, что он не принимает ничего другого.

К счастью, остальная часть аргумента проста, и мы, вероятно, могли бы сделать это в то же время, что и предыдущий.Это следует в том же формате.Предположим, наш NFA прибывает в одно из принимающих государств.Тогда это имеет вид (f1, f2).Это означает, что мы видели строку четной длины, где символы нечетного индекса, рассматриваемые вместе, вели к f1 в A1, а символы четного индекса приводили к f2 в A2.Но это означает, что последовательности принимали в соответствующих автоматах, и поэтому строка, которая привела нас к состоянию принятия на нашей машине, должна быть словом в L3.Мы только что утверждали, что NFA принимает не более строк на этом языке.

Поскольку наша машина принимает по крайней мере те строки, которые нам нужны, и, самое большее, строки, которые нам нужны, из этого следует, чтоон принимает именно те строки, которые нам нужны.

...