Рубрики

Проектирование конечных автоматов из регулярных выражений (набор 1)

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

  • Четное число a: регулярное выражение для четного числа a (b | ab * ab *) * . Мы можем построить конечные автоматы, как показано на рисунке 1.

    Вышеуказанные автоматы будут принимать все строки, имеющие четное число. Для нуля, это будет в q0, который является конечным состоянием. Для одного «a» оно перейдет с q0 на q1, и строка не будет принята. Для двух a в любых позициях он будет переходить от q0 к q1 для первого «a» и от q1 до q0 для второго «a». Таким образом, он будет принимать все строки с четным числом.

  • Строка с 'ab' в качестве подстроки: регулярное выражение для строк с 'ab' в качестве подстроки: (a | b) * ab (a | b) * . Мы можем построить конечные автоматы, как показано на рисунке 2.

    Вышеуказанные автоматы будут принимать все строки, которые имеют 'ab' в качестве подстроки. Автоматы останутся в начальном состоянии q0 для b. Он переместится на q1 после прочтения «a» и останется в том же состоянии для всех «a» после этого. Затем он перейдет к q2, если прочитано «b». Это означает, что строка прочитала 'ab' как подстроку, если она достигает q2.

  • Строка с числом «a», делимым на 3: регулярное выражение для строк с числом, делимым на 3: {a 3n | n> = 0}. Мы можем построить автоматы, как показано на рисунке 3.

    Вышеупомянутые автоматы примут всю строку формы 3n . Автоматы останутся в начальном состоянии q0 для ɛ, и они будут приняты. Для строки 'aaa' она переместится с q0 на q1, затем с q1 на q2 и затем с q2 на q0. Для каждого набора из трех a, он будет равен q0, поэтому принимается. Иначе, это будет в q1 или q2, следовательно, отклонено.

    Примечание. Если мы хотим создать конечные автоматы с числом a, равным 3n + 1, те же автоматы можно использовать с конечным состоянием как q1 вместо q0.
    Если мы хотим спроектировать конечные автоматы с языком {a kn | n> = 0}, требуется k состояний. Мы использовали k = 3 в нашем примере.

  • Двоичные числа, делимые на 3: регулярное выражение для двоичных чисел, которые делятся на три: (0 | 1 (01 * 0) * 1) * . Примерами двоичного числа, делимого на 3, являются 0, 011, 110, 1001, 1100, 1111, 10010 и т. Д. DFA, соответствующий двоичному числу, кратному 3, может быть показан на рисунке 4.

    Вышеупомянутые автоматы будут принимать все двоичные числа, делимые на 3. Для 1001 автоматы перейдут от q0 к q1, затем от q1 до q2, затем от q2 до q1 и, наконец, от q2 до q0, следовательно, принимаются. В течение 0111 автоматы перейдут из q0 в q0, затем из q0 в q1, затем из q1 в q0 и, наконец, из q0 в q1, следовательно, будут отклонены.

  • Строка с регулярным выражением (111 + 11111) *: строка, принятая с использованием этого регулярного выражения, будет иметь 3, 5, 6 (111 раз), 8 (один раз 11111 и 111 раз), 9 (трижды 111), 10 (дважды 11111) и все остальные подсчеты 1 впоследствии. DFA, соответствующий данному регулярному выражению, приведен на рисунке 5.

Вопрос: Каким будет минимальное количество состояний для строк с нечетным числом а?
Решение: Регулярное выражение для нечетного числа a — b * ab * (ab * ab *) *, и соответствующие автоматы приведены на рисунке 6, а минимальное количество состояний равно 2.

Оглавление | Проектирование детерминированных конечных автоматов (набор 1)

Эта статья предоставлена Sonal Tuteja.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Проектирование конечных автоматов из регулярных выражений (набор 1)

0.00 (0%) 0 votes