I need to write a CFG for the language below:
L = { w ∈ Σ* | w is a regular expression over a binary alphabet }
I came up with:
S = SΣ* | ε
X = S | ε
I'm starting the discipline now, and if it isn't correct, i would apreciate an explanation. Many thanks!
PS.: This is not part from a homework, it is just an exercise from a Computer Science Theory book.
ANSWER BASED ON Mo B. POST
S = e | {0,1}
X = S | S* | Z
Y = X | YX
Z = Y | Z | Y
SECOND ANSWER BASED ON Mo B. POST
S = e | {0,1}
X = S | S'*' | '(' Z ')'
Y = X | YX
Z = Y | Z '|' Y
No, this is not correct. The language is the set of regular expressions (which itself isn't regular, but it's luckily context-free), so you need to come up with a context-free grammar for regular expressions. (First, make sure you know the formal definition for regular expressions.)
The meta-alphabet Σ has not been defined in your question, but it only works if Σ at least contains the mentioned binary alphabet, say 0 and 1, and the symbols ε
, *
, |
, (
and )
.
Here is one way of doing it:
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