# Questions tagged [context-free]

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

202 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0answers
57 views

### Grammar for context free language

I want to give a grammar for the following language: $$L = \{x^r \# y |x, y \in \{a, b, c\}^*\\ \text{ and }x\text{ is a contiguous sub-string of }y\}$$ where $x ^ r$ denotes the backward written ...
0answers
66 views

### Prove by Pumping Lemma that Language $L=\{a^ib^kc^k : i\geq k\geq 1\}$ isn't Context-Free

I'm new to this forum. I have some difficulties on using Pumping Lemma to prove non-CF language. Let $L=\{a^ib^kc^k : i\geq k\geq 1\}$ and the followings are my attempt. Proof. Suppose by ...
0answers
174 views

0answers
37 views

### Prove the language L of all palindromes over {0,1} is in NP

Wouldn't this language be in P, since it is a context free language. And every context free language is a member of P? Or would it be otherwise?
0answers
103 views

### Is $\{ a^i b^j c^k : i + 1000\ < j + 100 < k \}$ context-free?

I have this language: $$L = \{ a^i b^j c^k : i + 1000\ < j + 100 < k \},$$ and what I believe is that we can't prove with the Pumping Lemma that it is not context-free, because we would ...
0answers
152 views

### Are there any context-free languages that are not regular but can be generated using a right-linear or left-linear grammar?

I understand that every regular language can be generated using either a right-linear or left-linear grammar, however, does that go the other direction? In other words, do there exist any context-free ...
0answers
39 views

### Computing the shortest path in a labyrinth

I'm currently trying to map how to make a good algorithm that won't have issues to find the shortest path. The labyrinth consists of an X and Y dimensions as input; However, the labyrinth will ...
0answers
109 views

### Polynomial time verifier for $\overline { EQ_{CFG}}$

How to find, or prove impossible, apolynomial time verifier for $\overline { EQ_{CFG}}$? $\overline { EQ_{CFG}}$ means all pairs G and H, which are CFGs such that L(G) is not equal to L(H)
0answers
457 views

### Deciding whether a context-free grammar's language is empty

Consider the formal problem: Given a context-free grammar $G$, is the language $L(G)$ empty? Can we determine if the problem is recursively enumerable, recursive, in NP, or in P? Can the entire ...
0answers
275 views

### Proving infinity of CFL with pumping lemma

Given a CFG G in Chomsky Normal Form with n variables. Prove that $|L(G)| = \infty \iff \exists w \in L(G)$ such that $2^n<|w|\le2^{n+1}$ Now, proving left to right I've encountered a problem. ...
0answers
186 views

### How to show that a language is strictly context sensitive

During a class, we was asked how to prove that a language L is strictly context-sensitive. In particular, we have to prove that $L = \{a^nb^nc^n \mid n > 0\}$ Could you help me to find the ...
1answer
531 views

0answers
148 views

### Reduction CVP to CFG problem

I want to show that non-emptiness of context free language is P-complete. So, I am trying to reduce CVP to this problem by generating grammar from circuit. I consider all type of gates in circuit and ...
2answers
69 views

### Determine if the language of words with same number of 1's and 2's is context-free or not

$$L_2=\{w \in \{0,1,2\}^* : \text{w has the same number of 1's and 2's}\}$$ I have tried creating PDA to determine if this was context-free or not. It seems like it would be because whenever a 1 ...
1answer
64 views

### Design a CFG that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }

I am trying to design a context-free grammar that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }. This is really confusing me, I'm having trouble with ...
1answer
41 views

### Transform grammar to Chomsky Normal Form

Question: S → abSab | baSba | TT T → aTa| bTb | ε My answer: Eliminate ε rules: S-> abSab | baSba | TT | T T-> aTa | bTb | aa | bb Correct answer: S → abSab | baSba | TT | abab | baba | T T → ...
1answer
28 views