The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
117 views

 

Help me to solve these questions 

asked in Theory of Computation by Junior (657 points)
edited by | 117 views
0
1. B)
3. I think L2 is regular
4. C)
I am not sure about the answers. Please confirm.
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

@Deepakpoonia(dee) 1st and 3rd  please help..?
+1
+1
0

@Deepakpoonia(dee) 1st and 3rd  please help..?

Done. Check the answer brother. 

0
thanks deepak..:)

1 Answer

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

answered by Boss (20.7k points)
edited by
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

Related questions

0 votes
0 answers
3
0 votes
0 answers
6
asked Aug 14 in Digital Logic by Vinnakota vineela (103 points) | 36 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,235 questions
49,718 answers
163,879 comments
65,834 users