3. I think L2 is regular

4. C)

I am not sure about the answers. Please confirm.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

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

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,751 questions

46,767 answers

140,663 comments

58,538 users