Как мне найти язык из регулярного выражения?

Question

Как бы я нашел язык для следующих регулярных выражений в алфавите {a, b}?

aUb*
(ab*Uc)
ab*Ubc*
a*bc*Uac

РЕДАКТИРОВАТЬ: Прежде чем я буду признан сумасшедшим, я был бы признателен, если бы кто-то мог показатьмне шаги к решению этих проблем, а не только решение.Может быть, даже проведя меня через один, чтобы я мог сделать все остальное самостоятельно.

Спасибо!

Answer 1

Редактировать: короткий ответ, * означает «ноль или более повторений» почти во всех синтаксисах регулярных выражений / грамматик, включая perl5 и RFC 5234. * обычно связывает более тесно, чем объединение и чередование.

Youскажем, вы хотите язык над алфавитом (a, b), но включите в свои выражения c и U.Я собираюсь предположить, что вам нужна грамматика языка над алфавитом (a, b, c) в форме, подобной BNF, с регулярным выражением, где U - оператор объединения с низким приоритетом, аналогично | в perlre.

В этом случае

a|b*

эквивалентно BNF:

L := a
   | <M>
M := epsilon
   | b <M>

Оператор * означает ноль илиболее того, первое предложение в M является базовым случаем, а второе предложение - рекурсивное использование M, которое включает в себя терминал b.

L - это просто один терминал a или нетерминал M.

(ab*|c)

L ::= a <M>
    | c
M ::= epsilon
    | b <M>

M выводится так же, как и выше, а остальное не требует пояснений.

ab*|bc*

L ::= a <M>
    | b <N>
M ::= epsilon
    | b <M>
N ::= epsilon
    | c <N>

N выводится так же, как и выше М.

a*bc*|ac

* в большинстве языков регулярных выражений связывается более тесно, чем конкатенация, так что это то же самое, что

(a*b(c*))|(ac)

, который сводится к

L ::= <M> b <N>
    | a c
M ::= epsilon
    | a <M>
N ::= epsilon
    | c <N>

В общем, чтобы преобразовать регулярное выражение в BNF, вы симply использует смежность в регулярном выражении для обозначения смежности в BNF, а U или | в регулярном выражении означает | в BNF.

Если вы определяете нетерминал <X> ::= x, тогда вы можете обрабатывать x* Таким образом:

L ::= epsilon
    | <X> <L>

С тем же нетерминалом <X> ::= x, тогда вы можете обрабатывать x+, таким образом:

L ::= <X>
    | <L> <X>

, что дает вам операторы повторения * и +который оставляет ?.x? это просто

L ::= epsilon
    | <X>

Answer 2

Хотя Майк дал грамматику, генерирующую языки, обозначаемые регулярными выражениями, ваше назначение запрашивает сами языки.Поскольку вы имеете дело с регулярными выражениями, ваши ответы должны быть регулярными.

Напомним определение регулярных наборов по алфавиту:

Let Σ be an alphabet. The class of regular sets over Σ is the smallest class
containing ∅, {λ}, and {a}, for all a ∈ Σ, and closed under union, concatenation,
and Kleene star.

Теперь вспомним определение регулярных выражений по алфавиту:

Let Σ be an alphabet. The class of regular expressions over Σ is the smallest
class containing ∅, λ, and a, for all a ∈ Σ, and closed under union, concat-
enation, and Kleene star.

Следовательно, переводдолжно быть простым.Фактически, это состоит из вставки фигурных скобок вокруг каждой буквы!Например:

a ∪ b*  denotes {a} ∪ {b}*
ab* ∪ c denotes {a}{b}* ∪ {c}
...

Если вы хотите выразить язык каждого регулярного выражения в нотации построителя множеств, вы можете вернуться к определениям операций над регулярными наборами.Напомним:

Let A and B be regular sets. Then
   1  A ∪ B = {x : x ∈ A ∨ x ∈ B}
   2. AB    = {xy : x ∈ A ∧ y ∈ B}
   3. A*    = ∪[i = 0 -> ∞]A^i

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

{a} ∪ {b}*    = {w : w ∈ {a} ∨ w ∈ ∪[i = 0 -> ∞]{b}^i}
{a}{b}* ∪ {c} = {w : (w = xy ∧ (x ∈ {a} ∧ y ∈ ∪[i = 0 -> ∞]{b}^i)) ∨ w ∈ {c}}
...

Теперь вы сможете найти языки, обозначенныеоставшиеся выражения без труда.

Answer 3

Если вы знаете, что означают звезда, объединение и соединение, это должно быть легко.Первый - это звезда b.В соответствии с порядком операций это означает объединение (звезда b).Союз означает что-либо на языке слева или что-нибудь на языке справа.a означает язык, состоящий из строки длины один;Звезда b означает язык, состоящий из любой строки, состоящей из нуля или более символов b и ничего больше.Таким образом, этот язык {пуст, a, b, bb, bbb, bbbb, ...}.Во втором ab * означает все строки, состоящие из a, за которым следует ноль или более b символов.Сначала делайте звездочку, затем конкатенацию, затем объединение, соблюдая заданные явные скобки.