FOR FREE CONTENT

Example 2

 

 Solution:

So, the machine cannot identify which one is the original string and which is a reverse string like abbbba

 

 

then it will be no problem to identify the main and reverse strings.

 

It has a comparison and at a time one comparison so, it follows LIFO order. But the push and pop are not clear, i.e. machine cannot understand when it does push operation and after which string it starts pop operations

 

In the previous example,  

here # identified the section for push and what section/string for pop.

 

 

We can take the reverse of it

The reverse is the same, so, it is a palindrome.

 

Example: 

Now it is even because 

 

Now how to identify the language:

In that case, we create multiple copies of machines i.e. we assume every symbol of string as the main string and push it on the stack and similarly, we assume the rest of the string is a reverse string then we are going to check push and pop operation is clear or not. If it clear i.e. stack is empty (in that case) then the string accepted otherwise rejected.

 

So, for every instance, we check the string is accepted or not. Here one string is accepted like abbbba in this situation. If one string is accepted by the machine, still machine will continue to till the end.

 

If at least one string accepted then we can say the string is accepted and it is Non-Deterministic Context-Free Language (NCFL).

 

 

Note: In NCFL, here it creates multiple copies of machines but no information is shared between copies of machines i.e. every machine works independently.