0
$\begingroup$

I was learned NPDA is specified by a tuple $P = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F) $,

  1. $Q$ is a finite set of states

  2. $\Sigma$ is a finite set of input symbols (input alphabet)

  3. $\Gamma$ is a finite set of stack symbols (stack alphabet)

  4. $\delta : Q × (\Sigma ∪ {\lambda}) × \gamma → 2^{Q×\Gamma^*}$ is the transition function

  5. $q_0$ is the start state

  6. $Z_0 \in \Gamma$ is the start symbol for the stack

  7. $F \subseteq Q$ is a set of final (or accepting) states

My Question

but in the solution of below problem, it just show the start and accepting states.

Is it enough?

Problem

Let $C$ be a context-free language and $R$ be a regular language. Prove that the language $C \cap R$ is context free.

Solution

Let $C$ be a context-free language and $R$ be a regular language. Let $P$ be the PDA that recognizes $C$, and $D$ be the DFA that recognizes $R$. If $Q$ is the set of states of $P$ and $Q'$ is the set of states of $D$, we construct a PDA $P'$ that recognizes $C \cap R$ with the set of states $Q \times Q'$. $P'$ will do what $P$ does and also keep track of the states of $D$. It accepts a string $w$ if and only if it stops at a state $q \in F_P \times F_D$, where $F_P$ is the set of accept states of $P$ and $F_D$ is the set of accept states of $D$. Since $C \cap R$ is recognized by $P'$, it is context free.

$\endgroup$
  • 2
    $\begingroup$ In general, mathematical proofs only tackles a level of detail deemed necessary for one to be sure of their correctness. In this case, the precise definitions you believe to be missing are in fact to be deduced from the high-level description in the proof's text. $\endgroup$ – dkaeae May 17 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.