0
$\begingroup$

I'm currently struggling to construct a nondeterministic PDA with an amount of states in $O(n)$ that accepts the following language: $L = \{wcx \, | \, w,x \in \{a,b\}^n \land w \not= x\}$ with c being a delimiter.

In lectures we discussed DPDA that accept $wcw^R$ or NPDA that guess the middle of the word with an $\varepsilon$-transtion and accept $ww^R$.

My idea has been to save $w$ in the stack but then I can't really assure the inequality of $w$ and $x$ then.

$\endgroup$
6
  • $\begingroup$ Have you searched thoroughly? I feel pretty confident this has been asked and answered before. See, e.g., cs.stackexchange.com/q/13866/755 $\endgroup$
    – D.W. ♦
    Jun 29, 2015 at 20:32
  • $\begingroup$ @D.W. You mean like this one? $\endgroup$
    – Raphael ♦
    Jun 29, 2015 at 20:40
  • $\begingroup$ Thanks for finding that, @Raphael! That's exactly what I was thinking of. $\endgroup$
    – D.W. ♦
    Jun 29, 2015 at 20:43
  • $\begingroup$ @D.W I looked for similar threads and found cs.stackexchange.com/q/307/ and cs.stackexchange.com/q/18774/ and I get the idea that the automaton uses it's non-determinism to check whether $w_i$ and $x_i$ are inequal - the length can be checked by pushing every letter on the stack and popping it later but how do I combine the two methods? $\endgroup$
    – PeterMcCoy
    Jun 29, 2015 at 20:44
  • $\begingroup$ @PeterMcCoy, in the future, if you know of approaches that you considered but rejected, or you know of other questions that partially answer your question or are relevant but you rejected for some reason, you should describe them in your question and explain why you rejected them or explain your particular uncertainty. We can't read your mind, so we can only go on what's written in the question. In your case, can you build a finite-state machine to check the length? Can you build a PDA to check that $w_i \ne x_i$? Do you know any facts about the composition of a FSM and a PDA? $\endgroup$
    – D.W. ♦
    Jun 29, 2015 at 21:00

0

Reset to default