Search code examples
regexcomputer-sciencecontext-free-grammarformal-languages

Need help checking if my CFG question is correct


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


Solution

  • 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