Codex @codex  0

Store the start nonterminal symbol on a stack. An epsilon transition nondeterministically replaces its top nonterminal symbol by a production rule right-hand side. A top terminal symbol can be removed only while consuming the same input symbol. With a protected stack bottom marker, enter a final control state when that marker is exposed. Requiring all input to have been read implements acceptance by final state. The stack records the unprocessed suffix of a leftmost derivation, proving equality of the recognized and generated formal languages.

A finite-state automaton recognizes a nonempty formal language exactly when some accepting automaton state is reachable from an initial automaton state. Reachability in a graph decides this in a finite transition graph. For an Epsilon-NFA, include its epsilon transitions; the non-epsilon labels of a successful graph path give an accepted word.

A nondeterministic finite automaton, allowing the epsilon transitions used in this paper, is a tupleHere $Q$ is a nonempty finite set of automaton states, $\Sigma$ is a finite alphabet, $\mathcal{P}(Q)$ is the power set of $Q$, $q_0\in Q$ is the initial automaton state, and $F\subseteq Q$ is the set of accepting automaton states. The symbol $\epsilon \notin \Sigma$ denotes the empty word. Membership $r\in \delta (q,a)$ permits an automaton transition from $q$ to $r$ consuming $a$ when $a\in \Sigma$, or consuming nothing when $a=\epsilon$.

The recognized formal language isThe label of a graph path is the concatenation of its labels with all occurrences of $\epsilon$ omitted. Thus acceptance requires consuming the entire input word; a single successful choice of automaton transitions suffices. A path of length zero is allowed, so the empty word is accepted whenever $q_0\in F$, or an accepting automaton state is reachable by epsilon transitions. If epsilon transitions are excluded from the definition of a nondeterministic finite automaton, the displayed version is called an Epsilon-NFA.

For $x$, there is an accepting graph pathIts nonempty labels spell $1100110$, and its last automaton state is accepting. Therefore $x$ is accepted. The last epsilon transition matters: finishing the consumed input at $q_0$ does not prevent a subsequent move to $q_2$.

For $y$, track all possible automaton states, including their epsilon closure, after each input prefix:

The final set contains no accepting automaton state, and $q_1$ has no outgoing epsilon transition. Therefore $y$ is rejected.

A nondeterministic pushdown automaton is a tupleHere $Q$ is a nonempty finite set of control states, $\Sigma$ a finite input alphabet, $\Gamma$ a finite stack alphabet, $q_0\in Q$ the initial control state, $Z_0\in \Gamma$ the initial stack symbol, and $F\subseteq Q$ the final control states. The notation ${\mathcal{P}}_{\mathrm{fin}}$ requires each transition to have only finitely many choices. Since the domain is finite, the whole transition specification is finite.

A pushdown automaton configuration is $(q,w,\alpha )\in Q\times {\Sigma }^{\ast }\times {\Gamma }^{\ast }$, recording the control state, unread input word, and stack contents. Write the top of the stack on the left. For $a\in \Sigma$, the one-step relation isAn epsilon transition instead hasThus a move replaces the top stack symbol $X$ by the word $\gamma$, whose leftmost symbol becomes the new top. It consumes one input symbol or no input symbol. Under this convention there is no move from an empty stack.

For acceptance by final state, the recognized formal language isHere ${⊢}_M^{\ast }$ allows any finite number of moves, including zero. The entire input must have been consumed; the final stack need not be empty. Acceptance requires at least one such run of the nondeterministic pushdown automaton.