A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# 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
2answers
46 views

### CFG where u has same number of 1s as v [closed]

$$L=\{uv\in\{0,1,2\}^*\mid u\in\{0,1\}^*,v\in\{1,2\}^*, \text{ and }u\text{ has the same number of 1s as }v\}.$$ Here is my attempt solution, but it is not completely correct, any hint is appreciated ...
1answer
75 views

### Is there a context-free grammar for $L = \{a^{2^n}| n \geq 1\}$? [duplicate]

I was trying to find a cf-grammar for $L = \{a^{2^n}| n \geq 1\}$ but I cannot seem to find one. Is there a cf-grammar or does it not exist because of the quadratic-exponent?
1answer
633 views

### Decidability of determining whether a context-free grammar generates all strings in 1*

How could I prove that the following language is decidable? $\{\langle G\rangle \mid G\ \text{is a CFG over}\ \{0,1\}\ \text{and}\ 1^* \subseteq L(G)\}$ P.S. It's the problem 4.15 of the third ...
2answers
52 views

### Context-free grammars for two languages

How do I write context-free grammars for the following languages? $B_2 = \{0^n1^n \mid n > 0\} \cup \{0^n1^{2n} \mid n > 0\}$ $B_3 = \{a^nb^mc^k \mid k = n+m\}$ Can someone help me? I'm not ...
0answers
13 views

0answers
43 views

### Is DCFL closed under union with RL? [duplicate]

So i know that DCFL is not closed under union, but what about union with RL? Because what if both of the languages can start with the same string?then when we are building the DPDA for the union and ...