Напишите регулярные выражения для следующих языков по алфавиту

Напишите регулярные выражения для следующих языков в алфавите ∑ = {0, 1}:

  1. Язык всех строк, которые не заканчиваются на 11.
  2. Язык всех строк, не содержащих подстроку 01. Также нарисуйте конечный автомат для каждого из вышеописанных языков.

computation-theory
person JAMIL AHMAD    schedule 20.11.2015    source источник
comment
Нет, я не хочу. А если серьезно, вы должны, по крайней мере, притвориться, что приложили некоторые усилия самостоятельно - показать нам, что вы пробовали, и объяснить, почему это работает не так, как вы ожидаете...   -  person twalberg    schedule 20.11.2015

Ответы (1)


arrow_upward
0
arrow_downward

Регулярное выражение для первого — e + 0 + 1 + S* (00 + 01 + 10), где e — пустая строка, S — алфавит, * — замыкание Клини, + — объединение. Это работает, потому что язык можно разделить на строки длины менее двух (e + 0 + 1) и строки длины не менее двух, которые не заканчиваются на 11 (при этом остаются окончания 00, 01 и 10).

Регулярное выражение для второго языка — 1*0*. Обратите внимание, что мы должны поместить любые 1 слева от всех 0, чтобы избежать подстроки 01, но мы можем иметь столько, сколько захотим.

DFA для первого будет выглядеть так

q    e    q'
q0   0    q0
q0   1    q1
q1   0    q0
q1   1    q2
q2   0    q0
q2   1    q2

Состояние q0 — начальное, q0 и q1 — принимающие. В состоянии q0 вы либо только что начали, либо в последний раз видели ноль; ваш последний символ не был 1. В состоянии q1 ваш последний символ был 1, но ваш предпоследний символ не был. В состоянии q2 вы увидели две единицы подряд.

DFA для второго будет выглядеть так:

q    e    q'
q0   0    q1
q0   1    q0
q1   0    q1
q1   1    q2
q2   0    q2
q2   1    q2

q0 — начальное состояние, а q0 и q1 — допускающие. q0 считывает все 0, q1 считывает все 1, а q2 происходит, если мы видим 0 после того, как увидели 1.

person Patrick87    schedule 20.11.2015