# Modify DFA/NFA that accepts Language Subset with only Palindromes (with Size Limit)?

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?

• What are your thoughts on the matter? What have you tried? Where did you get stuck? – Yuval Filmus Jul 16 '16 at 11:27
• 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. – TheoryQuest1 Jul 16 '16 at 11:34
• 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 – 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.