Question

3. Create a CFG describing regular expressions over the alphabet {0, 1}. You will need to quote the regular expression operators and the template given you has them quoted as terminals. We expect the grammar to generate the following syntactic constructions:

• Union via "|", for example, 0 1 "|" 1 should be in the language generated by the grammar

• Intersection via "&", for example, 0 1 "&" 1 should be in the language

• Concatenation: any nonempty sequence of regular expressions should be in the language

• The empty string, which is denoted with the terminal e. For example, 0 "|" e should be in the language

• Parentheses: for example, "(" 0 1 ")" should be in the language • Kleene star: for example, "(" 0 1 ")" "*" should be in the language

• Complement: for example, "-" "(" 0 "*" ")" should be in the language

Answer 1

We generate CFG describing regular expressions over {0,1}.

Let the generating symbol be S

(i) Basic alphabets like 0,1,e => _{$S \rightarrow 0 | 1|e$}

(ii) Union   => _{$S \rightarrow S "|"S$}

(iii) Intersection =>   _{$S \rightarrow S$} "&"  

(iv) Concatenation =>  
_{S → SS}

(v) Parentheses =>   _{$S \rightarrow "("S")"$}

(vi) Kleene Star =>   _{$S \rightarrow S^{"*"}$}

(vii) Compliment => _{$S \rightarrow$} "-"