recategorized by
631 views
2 votes
2 votes

Let $L$ be a context-free language generated by the context-free grammar $G = (V, \Sigma, R, S)$ where $V$ is the finite set of variables, $\Sigma$ the finite set of terminals (disjoints from $V$), $R$ the finite set of rules and $S \in V$ the start variable. Consider the context-free grammar ${G}'$ obtained by adding $S \rightarrow SS$ to the set of rules in $G$. What must be true for the language ${L}’$ generated by ${G}’$?

  1. ${L}'=LL$
  2. ${L}'=L$
  3. ${L}'=L^{\ast }$
  4. ${L}'=\left \{ xx \mid x \in L \right \}$
  5. None of the above
recategorized by

1 Answer

0 votes
0 votes

Correct Option: E


For starters, the language $L^{’}$  isn’t really the complement of $L$, it is defined by $G^{’}$ defined by adding a new-rule $S\to SS$.

So, for this problem let’s consider $L = \{ a, b, c \}$ (RG is a CFG) so we’ve a simple derivation $S\to a/b/c$, for $L^{‘}$ use the added rule which generates $L^{‘}=\{a,b,c,aa,ab…,cc,aaa,aab….ccc...\}$.

  1. Concatenation of every string of $L$ with every string of $L$ itself will produce $\{aa,ab,…,cc\}$ which is only a subset of the language $L^{‘}$.
  2. B.If this was true, we can’t generate $aa$ for instance, the $L^{‘}$ doesn’t only comprise the original elements but newly-generated too.C.
  3. The original language needn’t necessarily contain $\epsilon$, which in-turn can’t be used generated a $\epsilon$ int the new-language. The above Language provides the counter-example for this statement. So, not true...D.
  4. All strings generated by the above grammar do belong in $L^{‘}$ but, there are other elements such as $\{ab,ac,bc\}$ which aren’t generated so it isn’t true.E.
  5. None of the above options are true so?
edited by
Answer:

Related questions

2 votes
2 votes
1 answer
1
soujanyareddy13 asked Mar 25, 2021
462 views
Consider the following two languages.$\begin{array}{rcl} \text{PRIME} & = & \{ 1^{n} \mid n \text{ is a prime number} \}, \\ \text{FACTOR} & = & \{ 1^{n}0 1^{a} 01^{b} ...
1 votes
1 votes
2 answers
3
soujanyareddy13 asked Mar 25, 2021
566 views
Which of the following regular expressions defines a language that is different from the other choices?$b^{\ast }\left ( a+b \right )^\ast a\left ( a+b \right )^ \ast ab^...