Virtual Gate Test Series: Theory Of Computation - Languages

Question

Consider the following context-sensitive productions

$\\S\rightarrow bSb\, |\, AcA \\Ab\rightarrow A,\, Ab\rightarrow b \\bA\rightarrow b,\, bA\rightarrow A$

Let $G$ be grammar given by all the rules except the last, and let $G'$ be the grammar given by all the
rules mending the last. Which of the following is true?

1. $​L(G)$ is regular and $L(G')$ is context-free but no regular
2. $L(G)$ is context-free but no regular and $L(G')$ is regular
3.  Both $L(G)$ and $L(G')$ are regular
4.  None of $L(G)$ and $L(G')$ are regular

Answer 1

$G:\\S\rightarrow bSb|AcA\\ Ab\rightarrow A,Ab\rightarrow b\\bA\rightarrow b$

lets try to derive some string

$\\S\Rightarrow bSb\\\Rightarrow bbSbb\\\Rightarrow bbbSbbb\\.\\.(till\: any \: no\: of \: b's)\\\Rightarrow bbbAcAbbb$

Now on the left of c be have only one choice $bA\rightarrow b$, on right we have two choice $Ab\rightarrow A \: or\: Ab\rightarrow b$

So ,we will get

$\\S\Rightarrow bbbcAbb\: or\: bbbcbbb\\ further\\S\Rightarrow bbbcAb\: or\: bbbcbb\\further\\S\Rightarrow bbbcb$ 
No of b's on the right may be less.

so here$L(G) = \left\{b^mcb^n|m\geq n,m,n\geq 1\right\}$
$L(G)$ is Context Free

$G':\\S\rightarrow bSb|AcA\\ Ab\rightarrow A,Ab\rightarrow b\\bA\rightarrow b,bA\rightarrow A$

$\\S\Rightarrow bSb\\\Rightarrow bbSbb\\\Rightarrow bbbSbbb\\.\\.(till\: any \: no\: of \: b's)\\\Rightarrow bbbAcAbbb$

Now on the left of c be have  two choice $bA\rightarrow b\: or\: bA\rightarrow A$ ,on right we have two choice $Ab\rightarrow A \: or\: Ab\rightarrow b$

No of b's can vary on either side.
so here$L(G') = \left\{b^mcb^n|m,n\geq 1\right\}$
$L(G')$ is Regular,$b^+cb^+$.

Comments

got it !! thank u so much sir :)

Answer 2

Answer : B

The Given Grammar is Context Sensitive Grammar. And It means that the Expansion/Reduction of Any Non-terminal will depend on the Context. Like here, In $G$ and $G'$, We can say that $A$ will expand into $A$ only if $A$ is immediately followed by $b$ and then we can use the Production rule $Ab \rightarrow A$ which will replace respective $Ab$ by $A$.  

$G :$

$S \rightarrow bSb |AcA$

$Ab \rightarrow A, Ab \rightarrow b$

$bA \rightarrow b$

$S$ will go to  $b^nSb^n$, and then to generate a String, $S$ will expand into $AcA$, So, We can say that All the strings Generated by $S$ are of the form $b^nAcAb^n$

Now, Take Some value of $n$ and Observe the behaviour of  $b^nAcAb^n$

Say, $n = 4$, So, We have $S \rightarrow bbbb\,AcA\,bbbb$

Now, To generate a String, We need to vanish the non-terminal $A$. Observe that the former $A$(First $A$)  can only be Vanished by the Production rule $bA \rightarrow b$, Which means, Now we have $S \rightarrow bbbb\, cA\,bbbb$

Now, To vanish the remaining $A$(Second $A$ ), we can use either of the Two productions $Ab \rightarrow b $ or $Ab \rightarrow A $ ...

If you use $Ab \rightarrow b$ then $A$ will immediately vanish and we will have $b^4cb^4$. But if you use, $Ab \rightarrow A$, One $b$ will vanish and Now, To remove the $A$, we will repeat the same....i.e. Either Use $Ab \rightarrow b $ or $Ab \rightarrow A $. 

Which will give us $L(G) = \left \{ b^n c b^m | n \geq m, m \geq 1\right \}$ ..Which is Context Free and Non-regular.

---

$G' :$

$S \rightarrow bSb |AcA$

$Ab \rightarrow A, Ab \rightarrow b$

$bA \rightarrow b$, $bA  \rightarrow A$

$S$ will go to  $b^nSb^n$, and then to generate a String, $S$ will expand into $AcA$, So, We can say that All the strings Generated by $S$ are of the form $b^nAcAb^n$

Now, Take Some value of $n$ and Observe the behavior of  $b^nAcAb^n$

Say, $n = 4$, So, We have $S \rightarrow bbbb\,AcA\,bbbb$

Now, To generate a String, We need to vanish the non-terminal $A$. Observe that the former  $A$(First $A$)  can be Vanished by the Production rules $bA \rightarrow b$ or $bA \rightarrow A$. If you use $bA \rightarrow b$ then $A$ will immediately vanish and we will have $b^4cAb^4$. But if you use, $bA \rightarrow A$, One $b$ will vanish and Now, To remove the $A$, we will repeat the same....i.e. Either Use $bA \rightarrow b $ or $bA \rightarrow A $. 

Now, To vanish the remaining $A$(Second $A$ ), we can use either of the Two productions $Ab \rightarrow b $ or $Ab \rightarrow A $ ...

If you use $Ab \rightarrow b$ then $A$ will immediately vanish and we will have $b^4cb^4$. But if you use, $Ab \rightarrow A$, One $b$ will vanish and Now, To remove the $A$, we will repeat the same....i.e. Either Use $Ab \rightarrow b $ or $Ab \rightarrow A $. 

Which will give us $L(G') = \left \{ b^n c b^m | n, m \geq 1\right \}$ ..Which is Regular.  

Answer 3

Option D 

S-->bSb / AcA

Ab-->b / A

bA--> b / A

Now grammar G is 

S-->bSb / AcA

Ab-->b / A

S--> bⁿAcAbⁿ  Here Ab can be reduced to b or A

         but the first A can't be eliminated by any production

it means L(G) does not produce a single string