edited by
559 views
0 votes
0 votes

 

Help me to solve these questions 

edited by

1 Answer

3 votes
3 votes

Answer 1 : 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 2 : B

$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.



Answer  3 : B

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.



Answer 4 : C

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

edited by

Related questions

0 votes
0 votes
1 answer
2
Ravi_1511 asked Nov 8, 2016
544 views
If the set of all words over alphabet S is countable thenAny language over S must be finite.at least one language over must be uncountable.any language over S is countabl...
0 votes
0 votes
1 answer
4
amit166 asked Jan 28, 2023
340 views
which one true1. Determining whether context-free grammar is un-decidable2. Whether a given grammar is context-free is decidable