117 views

Help me to solve these questions

edited | 117 views
0
1. B)
3. I think L2 is regular
4. C)
0
4 is correct.

in 1 ans given is A

in 3 l1 is given regular l2 is not
0
Okay :(  Let's see what others answer..
0
for 2nd qsn answer should be B

+1
+1
0

0
thanks deepak..:)

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.

$A = \left \{ xy | x,y \in \left \{ a,b \right \}^*, n_a(x) = n_b(y) \right \}$

It is Regular. Moreover, $A = \Sigma^*$

Let's Prove it Formally :

Proof :

We can see easily(check manually) that $\in, a,b,aa,ab,ba,bb$ etc are in the language $A$ (i.e. We can split all these Strings in Two parts such that in the left part there are as many $a's$ as there are $b's$ in right part. Just check manually)

Two length strings can be partitioned as follows : $\left \{ |aa, a|b,b|a,bb| \right \}$

Now, All the Three length strings can be formed by appending $a$ or $b$ to the Two length strings and We already have some partition of Two length strings. So, Here goes the Idea :

"If we append $a$ at the end of any Two length string then the Previous Partition of the Two length string will remain as it is"

i.e. $\left \{ |aaa, a|ba,b|aa,bb|a \right \}$

"If we append $b$ at the end of any Two length string then the Previous Partition of the Two length string will shift to right by One Position"

i.e. $\left \{ a|ab, ab|b,ba|b,bbb| \right \}$

So, We can inductively say that ""If we append $a$ at the end of any $n-1$ length string then the Previous Partition of the $n-1$ length string will remain as it is" and "If we append $b$ at the end of any $n-1$ length string then the Previous Partition of the $n-1$ length string will shift to right by One position"

Hence, We can say that Every string can be Partitioned in Two parts such that  in the left part there are as many $a's$ as there are $b's$ in right part. So, $A = \Sigma^*$

$B$ is Simple and Standard Non-regular CFL.

https://cs.stackexchange.com/questions/65176/check-the-regularity-of-the-folowing-languages

I don't know the reasoning for $L_1$ right now. But I can easily say that $L_2$ is Not Regular.

Consider $A = ab^*$

Now, $L_2 = (a)^* + (ab)^* + (abb)^* + (abbb)^* + ....$ Which is Non-regular.

Either we could eliminate Options $a,b$. Or we could use $FA$ to $RE$ algorithms and we will get answer as Option $C$.

edited
0
Thanks ..I also got B for the first question but the answer given is A he told. Now got confirmed. :)
0
answer given in key was wrong ,thanks a lot

1