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

Question

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?

Answer 1

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.