Given a DFA (D1) with P1 states, that accepts a language L1.

Modify (D1) to create another DFA (D2), such that it will accept the language L2 that is defined as: All strings in L1 that are also a palindrome (of maximum length P1).

How many states would the minimized D2 have (worst case)? And time complexity?

Similarly, NFA (N1) with Q1 states that accepts a Language L3. How many states would minimized (N2) have (worst case)? Along with its time complexity?

The generic Palindrome Language is non-Regular hence a DFA/NFA for it is impossible but I am unaware of the limited Palindrome case in DFA/NFA?

  • 1
    $\begingroup$ What are your thoughts on the matter? What have you tried? Where did you get stuck? $\endgroup$ – Yuval Filmus Jul 16 '16 at 11:27
  • $\begingroup$ As the DFA has no memory, I suppose we would have to create a seperate state for every character if we were just testing for a Palindrome of a specific Size in D2. But, since we are testing both for L1 and Palindrome property, I am lost at how to approach it and its size and space complexity wrt. D1 in the worst case. $\endgroup$ – TheoryQuest1 Jul 16 '16 at 11:34
  • $\begingroup$ We can go ahead, enumerate all possible strings in L1, then find a subset of Palindromes in it and construct a DFA (D2), but i simply dont find it efficent since we already have D1 $\endgroup$ – TheoryQuest1 Jul 16 '16 at 11:36

For DFAs, the size of $D_2$ is always at most $O(P_1|\Sigma|^{P_1/2})$, and this bound is tight up to the $P_1$ factor. For the lower bound, take a DFA for $\Sigma^*$ having $P_1$ states (you haven't specified that $D_1$ is minimal). The DFA $D_2$ accepts all palindromes of length $P_1$, and so Nerode's theorem shows that for even $P_1$, the optimal DFA $D_2$ contains $\Theta(|\Sigma|^{P_1/2})$ states. The upper bound now follows by using the product construction.

The exact same reasoning works for NFAs as well, although you need to replace Nerode's theorem with a suitable "exchange lemma" in order to show that any NFA for the language of all palindromes of length $P_1$ requires $\Omega(|\Sigma|^{P_1/2})$ states (for even $P_1$).

If you insist on $D_1$ being minimal as well, then instead of a DFA for $\Sigma^*$ take a DFA for $(\Sigma^{P_1})^*$, to get the exact same results. This construction works also for NFAs.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.