FOR FREE YEAR SOLVED

Important Exercise and Solutions

Identify the language:

Solutions:  

Answer:

This same problem already discussed in Example 2 please see for details.

And because there is no special character so, it needs multiple copies of the stack. 

For details see Example 2.

Answer:

The type of language is similar to the above language. 

Example: abbabba. 

But in the previous example, it was even palindrome.

But here same like the previous example, we need multiple copies of the machine because middle (a + b) is not working as a special character, it also part of the string where ∑ = {a, b}.

In that case, is the same previous example we can’t recognize – 

We should create various copies of machines. 

This language also a set of palindrome but in that case all palindrome string (even and odd) i.e. set of all even and odd palindrome string.

Previously we have already seen a set of even palindrome and set odd palindrome distinctly.

Now it is a set of all palindrome string (even and odd), Example: abba, aba

Set of all even palindrome – one machine work for it

Set of all odd palindrome – one machine work for this

In this case, also we need multiple copies of the machine.

Actually, 

We already solve the same problem in Example 1 please see the details. 

Because of the special symbol # which is not a direct part of the language (not belongs to ∑), we can identify which one is an original string and which is a reverse string.

So, by a single stack, we can solve the problem i.e. push and pop are cleared.

Because of one comparison and push, pop is cleared.