# Questions tagged [context-free]

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

1,483 questions
Filter by
Sorted by
Tagged with
47 views

### Proving language is not context-free with pumping lemma

I'm trying to prove that this language is not context free using pumping lemma. I am having difficulty as to where to even start on this. $$\{c^{2i} d^j b^{2j} d^k c^{3j} \mid i,j,k \ge 0\}$$
24 views

### A function that maps a context-free grammar G to the context-free grammar G′ [closed]

So i'm really lost on this exercise: Let f be the function that maps a context-free grammar G = (V,Σ,S,P) to the context-free grammar G′ = (V,Σ ∪{a},S,P′), where P′ = P ∪{S →SS}∪{X →a |X → ∈P}. Give f(...
10 views

### Finding out the language generated by a context-free grammar

how can i find out the language that accepted by this cfg : S -> A B | B C A -> B A | x B -> C C | y C -> A D | x D -> y
34 views

### References to deterministic time complexity of language classes

It's fairly well known that $REG \in TIME(n)$. I would like to know similar inclusions for the language classes $DCFL$ and $CFL$. I have found a variety of claims for these classes on the internet. ...
52 views

31 views

### I can't visualize what happens when we pump v and y in pumping lemma for $a^n b^n c^n$

If you need some context-: https://www.andrew.cmu.edu/user/ko/pdfs/lecture-11.pdf around page 7. Case 1-: Say vxy contains ab So when I pump v and y, what will get pumped? And how the result would be. ...
29 views

### CFG for L={a^i b^j c^i; i,j > 0}

I worked a bit on this and got this-: S->ABC A->aA/a B->bB/b C->cC/c The obvious problem here is I am unable to count number of a's and c's which ...
33 views

### I need a pumping lemma for context free lenguages for this example? [duplicate]

Prove is that a context free lenguage or not $L=$ { $0^k 1^l 0^k; k\geq l; (k,l) ∈ N ∪ 0$ }
116 views

### Can I solve pumping lemma for context free language proofs using examples?

Say I need to prove that $L=${$a^n b^n c^n; n\geq 1$} is not context free language I take n=3. w=aaabbbccc Here |w|=9. we know by pumping lemma-: |vxy| $\leq$n so vxy=abb |vy| $\geq$1 so vy=ab Hence I ...
13 views

### Tips on making a grammar LL(1)?

So I currently am given the following grammar, and I have to make it LL(1). To do this, I need to remove ambiguities, eliminate left recursion, and left factor if necessary. But looking at this, it's ...
19 views

### What is the subset of CFGs called where each expansion must be the same?

I was wondering about a kind of grammar where we can expand rules of the form A -> X|Y|... with A being a nonterminal and <...
40 views

### Is language $a^mb^nc^n, m \not= n$ context free

I need to say Is language $a^mb^nc^n, m \not= n$ context free I managed to find a grammar for $L1 =$ { $a^lb^mc^n | l=m$ or $m = n$ }, but I couldn't find the one I needed. Maybe it is impossible, ...
42 views

63 views

### Proving that $\{ a^i b^j c^{\max(i,j)} \}$ is not context-free

Prove that $L$ is not a Context-free language, where $$L = \{ a^{i} b^{j}c^{h}\mid i,j,h\in \mathbb{N} \wedge h = \max(i,j)\}.$$ I have an idea: It can be divided into two situations: When $i < j$...
39 views

### In what sense is a CFDG grammar a context free grammar?

CFDG is described as a language for context free grammars which can generate images. It allows rules to have parameters, but places restrictions on them to ensure the grammar is context free rather ...
### If $p(n) := \sum_{i=0}^ka_in^i$ where $a_i\in\mathbb{N}, a_k \ne 0$ AND $k \ge 2$, is $L = \{0^n1^{p(n)} \mid n\in\mathbb{N}\}$ context-free?
I have the really strong feeling it is indeed NOT context-free, since the language $1^{n^k}$ for $k\ge 2$ is not context free (proven by the pumping lemma) and, in a sense, "the order of ...