Нужна помощь в проверке правильности моего вопроса о CFG

Мне нужно написать CFG для языка ниже:

L = { w ∈ Σ* | w is a regular expression over a binary alphabet }

Я придумал:

S = SΣ* | ε

X = S | ε

Я начинаю дисциплину сейчас, и если это не правильно, я был бы признателен за объяснение. Большое спасибо!

PS.: Это не часть домашнего задания, это просто упражнение из книги по теории информатики.

ОТВЕТ НА ОСНОВЕ МО Б. ПОСТ

S = e | {0,1}

X = S | S* | Z

Y = X | YX

Z = Y | Z | Y

ВТОРОЙ ОТВЕТ НА ОСНОВЕ МО Б. ПОСТ

S = e | {0,1}

X = S | S'*' | '(' Z ')'

Y = X | YX

Z = Y | Z '|' Y


regex computer-science context-free-grammar formal-languages
person beto99    schedule 05.12.2020    source источник

Ответы (1)


arrow_upward
3
arrow_downward

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

Мета-алфавит Σ не был определен в вашем вопросе, но он работает только в том случае, если Σ по крайней мере содержит упомянутый двоичный алфавит, скажем, 0 и 1, и символы ε, *, |, ( и ).

Вот один из способов сделать это:

Basic   ::= 'ε'   // Note that this is the symbol 'ε' which is not the same as ε
          | c     // for c in {0, 1} or whatever the binary alphabet is
Star    ::= Basic
          | Star '*'
          | '(' Regular ')'
Concat  ::= Star
          | Concat Star
Regular ::= Concat
          | Regular '|' Concat
person Mo B.    schedule 05.12.2020
comment
Я не отрицал ваш ответ. На самом деле, большое спасибо за это, у меня недостаточно репутации, чтобы проголосовать за вас. Не могли бы вы помочь мне с правильным ответом на этот вопрос? Спасибо. - person beto99; 05.12.2020
comment
@beto99 Что ж, это это правильный ответ. Или еще что-то непонятно? - person Mo B.; 05.12.2020
comment
Мо Б., проверьте, совпадает ли ответ на мой вопрос с вашим, пожалуйста. - person beto99; 05.12.2020
comment
Почти, но не совсем. Вы должны убедиться, что отличаете символы от метасимволов, например. |, *, (, ) или ε. Используйте апострофы, чтобы сделать различие. Во-вторых, в вашем втором случае отсутствуют скобки ( и ). - person Mo B.; 05.12.2020
comment
Мо Б., большое спасибо. Я думаю, что мы, наконец, сделали это. - person beto99; 05.12.2020
comment
@MoB.: Получите (a|b)* из этой грамматики. Если вы можете это сделать, я уберу DV. - person rici; 06.12.2020
comment
@rici Спасибо за подсказку. Я исправил ошибку. Когда вы понижаете голос, добавьте комментарий, если причина не очевидна. В противном случае это не очень полезно. - person Mo B.; 06.12.2020