Question

Consider creating an NFA for the following language L = { ww^(R) | w∈{0,1}* }. What problems do you encounter when attempting to create this automaton, why do you encounter
them and what does that mean for the existence of this NFA? Please explain your answer in detail.

Answer 1

L = { ww^(R) | w∈{0,1}* }.

When a language is given, we can consider building an NFA part by part.

• Let's take { w | w∈{0,1}* }.

We can take a state for this which is initial state A and can have slef loop over 0 and 1.

• Let's take the later part { w^(R) | w∈{0,1}* }.

To get this, we need w in reverse order.

-> We have w which can be read only once
-> w can't be read from right side to know the reverse of it

So, either we need memory or we should be able to read the string any number of times to get this done.

But with NFA neither of them is possible.
So, there doesn't exist any NFA which accepts this language.

-- Please up vote or comment if you have any doubts. Happy Learning!