# Questions tagged [context-free]

Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.

1,197 questions
Filter by
Sorted by
Tagged with
99 views

### Can the String, $0^p 0^p 0^p$, be Used with the Pumping Lemma to Show that $w^r w w^r$ is Not Context Free?

I'm trying to show that $L=\left\{w^rww^r:w \in \{0,1\}^*\right\}$ is not context free using the pumping lemma. I thought picking the string, $0^p0^p0^p$, would be a good candidate for this, but ...
311 views

1k views

### Does Reverse Polish Notation have an LL grammar?

Let L be the language of all arithmetic expressions written in Reverse Polish Notation, containing only binary operators. $\Sigma(L) = \{n, o\}$, n := number, o := operator. Is there an LL grammar G ...
90 views

### Grammar generating specific language

Construct a context-sensitive grammar that generates L: L = {a^n b^m c^k|k>n, k>m} I believe my productions should go along this lines: ...
55 views

### Which grammar is this?

Having the grammar G = (V,P,S) with variable V = {S,A} over the alphabet {a,b} with the ...
1k views

### Is the Syntax of C Language completely defined by CFGs?

I think the Question is self sufficient. Is the syntax of C Language completely defined through Context Free Grammars or do we have Language Constructs which may require non-Context Free definitions ...
236 views

### What does this context-free grammar generate?

The grammar is $$S\to aSb\ |\ bSa\ |\ SS\ |\ \epsilon.$$ I think this generates the set of strings with equal numbers of $a$'s and $b$'s based on examples I've done. Is this correct?
2k views

### How to prove every context-free language over a unary alphabet is regular?

How can I show that every context-free language over a unary alphabet is regular?
### The complement of $\{w: w\text{ has equal numbers of$a$'s,$b$s' and$c$'s}\}$ is context-free
Let $L$ be the language $\{w \mid w \text{ has equal numbers of $$a$$'s, $$b$$'s and $$c$$'s}\}$. Prove that its complement $\overline{L}$ is context free.