# Questions tagged [context-free]

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

1,578 questions
Filter by
Sorted by
Tagged with
10 views

### Can the leaf nodes of a parse tree be labeled by a variable, a terminal, and the empty symbol; or only a terminal and the empty symbol?

When you are deriving a string using a context-free grammar (CFG), you start with the start symbol and at the right side you have combinations of variables (non-terminals) and terminal symbols. Let's ...
23 views

### How to use Pumping Lemma $L = { wsw | w ∈ {0,1}*, s ∈ {2}*, and |w| = 2 * |s| }$?

I'm trying to use the Pumping Lemma to prove that $L = { wsw | w ∈ {0,1}*, s ∈ {2}*, and |w| = 2 * |s| }$ is not a CFL.
24 views

### How to use Pumping Lemma for L={www|w∈{0,1}* and w starts with 0}?

I know my question might be a bit similar to How to use Pumping Lemma for $L = \{www | w∈\{0,1\}^*\}$ However, I feel that it is different enough due to the extra requirement of starting with 0
42 views

### proof that every sentence obtainable by left-most derivations only when Greibach normal form

Could someone help me prove the following statement: “For any grammar in Greibach normal form, every sentence is obtainable by left-most derivations only.” I see that this is trivial, but I can't ...
1 vote
67 views

### How are regular languages not structurally recursive?

This blog posting states that "regular languages aren't structurally recursive" while "That's not the case for context-free grammars" In what sense is the term "structurally ...
1 vote
131 views

### How to prove the language of words $a^ib^jc^k$ where $\min(i,j)\le k\le\max(i,j)$ is not context-free?

I want to prove that $\mathcal M =\{a^ib^jc^k \mid \min(i,j)\le k\le\max(i,j)\}$ is not a CFL. Using the pumping lemma, let $p$ be the constant, then I choose $w=a^pb^pc^p$. When I separate to cases, ...
1 vote
36 views

### substitution of same variable in context-free grammars

Above is a theorem coming from the book "Formal languages and automata" by Peter Linz concerning substitution of variables. Could someone explain why A and B have to be different variables?
41 views

### Why is $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ a regular language?

Define $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ while $\#\notin \Sigma$ Why is $L'$ a regular language? I have tried to construct the DFA of L, then with a # move to a copy of this DFA with flipped ...
1 vote
74 views

### variable repetitions in pumping lemma for context-free languages

Above is the proof of the pumping lemma for context-free languages, coming from the book 'Formal Languages and automata' by Peter Linz. The picture below is in support of the proof. I do not ...
15 views

37 views

### If two states of a DFA are k-equivalent and k+1 equivalent

Let $p,q$ be two states of a DFA, such that $p\equiv_kq$ and $p\equiv_{k+1}q$. Does it mean that $p\equiv q$ ? I don't think so, because if the minimization algorithm can continue, they might be ...
48 views

### Prove or disprove that $\{xc o(x) :x \in A\}$ is context-free, where A is a regular language

Suppose o is a map on strings to strings. For every language R, we let $o(R) := \{o(x) : x \in R\}$. If o(R) is a regular language for every regular language R, then prove or disprove that the ...
127 views

### Find a Context-Free Grammar for $L = \{a^wb^xc^yd^z | w + x = y + z\}$

I have to find a CFG for the given expression: $L = \{a^wb^xc^yd^z | w + x = y + z\}$ This is what I've tried so far: S -> aSd | B | ϵ B -> bBc | ϵ It works for expressions like: aabcdd, ...
1 vote
40 views

### If $L$ is regular then $\{x~|~\exists y ~~s.t~~ xyx^R \in L\}$ is regular

Prove/disprove the following claim: If $L\in RL$ then $\{x~|~\exists y ~~s.t~~ xyx^R \in L\} \in RL$ I think that this is true, and my intuition is by using $L_{pq}$ s.t: For every $(p,q)\in Q\times Q$...
1 vote
173 views

### How to prove that $half(L)=\{x|xy\in L,|x|=|y|\}$ is Regular Language

Let $L$ be a regular language. Define: $half(L)=\{x|xy\in L,|x|=|y|\}$ Prove that $half(L)$ is regular as well. I have seen a hard proof by using the DFA A of L, building a NFA B (such that every ...
80 views

### Are the set of all Bitcoin addresses a context-sensitive language?

This started with me trying to make a regex to accept Bitcoin addresses. However, I couldn't do it. That led me to think: "is the set of all possible Bitcoin addresses even a regular language&...
1 vote
75 views

72 views

### Possible PDA for $L = \{ a^{3n}b^{2n} | n \ge 0 \}$ without transforming CFG to PDA

To those of you who saw my post from an hour ago - I deleted it because I came up with an idea. To summarize, I have to design a PDA for this language, without using the usual method of firstly ...
1 vote
57 views

### Designing a PDA without using CFG -> PDA for the language $\{ a^nb^m | n \le m \le 2n \}$

$L= \{ a^nb^m | n \le m \le 2n \}$ As you may recall, I posted a question a few hours ago about designing a PDA for a language similar to the one I have now. I have seen that the easiest way to ...
51 views

### CFG to RG Conversion

I'm struggling with this question. I would appreciate a detailed solution as it would help me better understand the subject. Convert the following Context Free grammar into a Regular Grammar: S -> ...
### show that $L=\{a^*\}\cup\{b^ja^{n^2}|0<j,1\leq n \}$ Holds the pumping lemma for context-free languages
prove this language verifies the conclusion of the pumping lemma show that $L=\{a^*\}\cup\{b^ja^{n^2}|0<j,1\leq n \}$ Holds the pumping lemma for context-free languages the problem is that I ...