需要帮助检查我的 CFG 问题是否正确

Question

我需要为以下语言编写 CFG：

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

我想出了：

S = SΣ* | ε

X = S | ε

我现在开始管教了，如果不正确，我会很感激你的解释。非常感谢！

PS.: 这不是家庭作业的一部分，它只是计算机科学理论书中的练习。

答案基于 Mo B。POST

S = e | {0,1}

X = S |年代* | Z

Y = X | YX

Z = Y | Z | Y

基于 Mo B 的第二个答案。POST

S = e | {0,1}

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

Y = X | YX

Z = Y | Z'|' Y

Answer 1

不，这是不正确的。该语言是 正则表达式 的集合（它本身不是正则的，但幸运的是它是上下文无关的），因此您需要为正则表达式提出一个上下文无关的语法。（首先，确保您知道正则表达式的 formal definition。）

元字母表 Σ 尚未在您的问题中定义，但它仅在 Σ 至少包含提到的二进制字母表（例如 0 和 1）以及符号 ε、[=12= 时才有效]、|、( 和 ).

这是一种方法：

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

需要帮助检查我的 CFG 问题是否正确

Need help checking if my CFG question is correct

regex

computer-science

context-free-grammar

formal-languages