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 can construct a PDA P’ that recognizes C ∩ R with the set of
states Q ⨯ Q’. P’ will do what P does and also keep track of the states of D. It will accept
a string w iff it stops a a state q ∊ FP⨯FD, where FP is the set of accept states of P and FD is
the set of accept states of D. Since C ∩ R is recognized by P’, it is context free.
Let A = {w | w ∊ {a, b, c}* and w contains equal numbers of a’s, b’s, and c’s}. Use the fact
that C ∩ R is context free to show that A is not a context free language.
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 can construct a PDA P’ that recognizes C ∩ R with the set of
states Q ⨯ Q’. P’ will do what P does and also keep track of the states of D. It will accept
a string w iff it stops a a state q ∊ FP⨯FD, where FP is the set of accept states of P and FD is
the set of accept states of D. Since C ∩ R is recognized by P’, it is context free.
Let A = {w | w ∊ {a, b, c}* and w contains equal numbers of a’s, b’s, and c’s}. Use the fact
that C ∩ R is context free to show that A is not a context free language.