Need help checking if my CFG question is correct

user_14769781 0
Viewed 140

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

formal-languages computer-science context-free-grammar regex
1 Answers

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
user_6899230
Related