retagged by
1,394 views
0 votes
0 votes

The CFG $S \to aS\mid bS\mid a\mid b$ is equivalent to 

  1. $(a+b)$
  2. $(a+b)(a+b)^*$
  3. $(a+b)(a+b)$
  4. all of these
retagged by

1 Answer

4 votes
4 votes
(A)-does not generate strings  $babb,abb$ etc.  but CFG generates it.(This option generates only 1-length strings)

(B)- is the answer

(C)-it only generates 2-length strings and other strings generated by the CFG are not generated by this regular expression.

So, B is correct.
Answer:

Related questions

1 votes
1 votes
2 answers
1
admin asked Mar 31, 2020
1,672 views
If there is in NP-Complete language L whose complement is in NP, then complement of any language in NP is inPNPboth (A) and (B)None of these
2 votes
2 votes
2 answers
2
admin asked Mar 31, 2020
1,872 views
Which of the following regular expressions denotes a language comprising all possible strings over the alphabet $\{a,b\}$?$a^*b^*$$(a\mid b)^*$$(ab)^+$$(a\mid b^*)$
2 votes
2 votes
4 answers
4
admin asked Mar 31, 2020
903 views
If $L_1$ and $L_2$ are context free language and $R$ a regular set, then which one of the languages below is not necessarily a context free language?$L_1L_2$$L_1\cap L_2$...