Skip to main content
6 votes

Is the complement of this context-free language also context-free?

Here's a somewhat simple, non-constructive approach. Try to convince yourself, that $\mathcal{G}$ generates a deterministic context-free language. Since all deterministic context-free languages are ...
Knogger's user avatar
  • 1,372
5 votes
Accepted

Is the complement of this context-free language also context-free?

Summary The above context free grammar $\mathcal{G}$ has an equivalent pushdown automation $M$. As the starting letters of $u$ and $v$ are different ($a$ and $b$), we can create a $M$ which is a ...
EnEm's user avatar
  • 664
4 votes
Accepted

Should a PDA reject words not in language?

If your PDA, $M$, accepts words not in the language, $L$, then $M$ is not a PDA for the language $L$. However, I don't think your "counterexample" is an actual counterexample. By that, I ...
NaturalLogZ's user avatar
3 votes
Accepted

Are Context-Free languages closed under XOR?

Rather than directly using the pumping lemma, you can use the closure property of context-free languages. I use $L_1 := \{1^{2n}0^n \mid n \geq 0\}$ and $L_2 := \{1^n0^{2n} \mid n \geq 0\}$ to show $L ...
pcpthm's user avatar
  • 2,817
3 votes
Accepted

Question about a grammar who generates $(0+1)^*$

We can prove this using mathematical induction. For base case, it is easy to see that $S$ can generate $\varepsilon, 0, 1, 00, 11, 01, 10$. Now we assume $S$ can generate any binary string on $0$s and ...
codeR's user avatar
  • 1,797
2 votes

Possible mistake in a book regarding parsing and lexical analysis

That statement does seem like a mistake. Context-free grammars are more relevant to parsing, whereas lexing is mainly driven by regular expressions, as evidenced by parser generators such as yacc and ...
Li-yao Xia's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible