Let language $L=\{\sigma_1w_1c\sigma_2w_2c...\sigma_nw_nc\}$ where: $$ 1\le n\\ \sigma_i\in \{a,b\}\\ w_i\in \{a,b\}^+\\ \exists i:i\le|w_i| $$ and at least one condition from the two conditions below holds:
the first $i$ letters of $w_i$ form a different word from $(\sigma_1\sigma_2...\sigma_i)^R$ OR $|w_i|=n$.
Build a pushdown automaton which receives $L$ by emptying its stack.
The solution of these two conditions separately is here: https://i.stack.imgur.com/dLwvr.jpg.
As far as I understand in the automata for both condition 1 and condion 2 ($|w_i|=n$) essentially:
- We build an automaton which simply describes reading $\sigma, w_i, c$ first.
- Then we guess the $w_i$ which is according to condition 1 or 2.
- Then we read the $\sigma, c$ surrounding the guessed $w_i$ and the $w_i$ itself.
I'm new to pushdown automata, but it looks like a lot of automata could be solved in such a generic way:
- Read the words according to some logic described in the problem.
- guess some "good" word (by using $\epsilon$ connection) and delete it from the stack.
Am I missing something?
Also I don't understand why we need $2$ cases in the solution for each condition. The solutions for each condition look almost identical.
Lastly, I don't understand why in the automaton for the condition $1$ in state $q_5$ we need to read the end of $w_i$ first, then read the "good" $w_i$. Why can't we read the "good" $w_i$ straight after the guess?