Questions tagged [context-free]
Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.
1,681
questions
2
votes
2
answers
239
views
Intuition for Sipser's proof of PDA to CFG
I understood Sipser's proof of CFG to PDA but I am having a hard time understanding his proof of conversion from PDA to CFG while demonstrating the equivalence between the two.
He splits the proof (...
- 33
0
votes
1
answer
90
views
proving a step in the proof of regular intersection
Let $L_1$ be a context-free language and $L_2$ be a regular language. Then $L_1 \cap L_2$ is context-free.
Part of a proof given in the book "Formal languages and automata":
Let $M_{1}=\left(...
- 89
0
votes
1
answer
88
views
Greibach Normal Form: Proof every sentential form is of the form xy with x terminals and y variables
For any grammar in Greibach normal form, every sentential form obtained from S by a partial left-most derivation is of the form xy with x terminals and y variables.
I think that this can be proven ...
- 89
0
votes
0
answers
360
views
Non-deterministic Pushdown Automaton to Context-Free Grammar
While doing the exercise about questions about transforming NPDA to CFG, I encountered the following question:
Find a CFG for the following NPDA $M = (\{q_0, q_1\}, \{a, b\}, \{A, z\}, \delta, q_0, z, ...
- 101
-1
votes
1
answer
46
views
Pumping lemma for context-free languages: Importance of length restriction
(from 'An Introduction to Formal Languages and Automata' by Peter Linz)
What I do not understand, is why we have done our best to make sure that the condition (8.2) holds. Why is this restriction ...
- 89
2
votes
1
answer
119
views
What role does an asterisk serve in Backus–Naur Normal Form?
Suppose that you were reading some production rules for a context-free grammar in Backus–Naur Normal Form
What does the asterisk (*) mean?
In the example below, ...
0
votes
1
answer
90
views
How can we escape the pipe character in Backus–Naur Normal Form?
Suppose that you were writing down the syntax rules for something like C++ as a context-free grammar in Backus–Naur Normal Form
How can you distinguish between the pipe character as symbol in C++ or ...
1
vote
2
answers
277
views
How to disambiguate CFG with unary/binary minus and binary prefix operator
I'm designing an expression language that's trying to (a) be maximally compatible with a different ambiguous language; and (b) be LR(1).
I'm facing the current fragment of the language:
$$
\begin{...
- 709
1
vote
1
answer
323
views
determining whether a context-free language is regular
I was wondering how to determine (with proof) whether the context-free language generated by the following context-free grammar $G$ is regular, where $S$ is the start variable and $a$, $b$ are the non-...
- 289
1
vote
1
answer
40
views
if $RA$ is context-free, is $A$ context-free?
If $RA$ is context-free for a regular language R, is $A$ context-free?
I think this statement is true. Let G be the CFG given by the rules $S_0\mapsto LA_1, S\mapsto LA_1, A_1\mapsto SA_2 | RS | 1, ...
- 289
0
votes
1
answer
54
views
prove that the unique language $A$ such that $AB$ is context free for all languages B is the empty set
Prove that the unique language $A\subseteq \Sigma^*$ such that $AB$ is context free for all languages $\subseteq \Sigma^*$ is the empty set.
If $A$ is not the empty set, there should be a way to ...
- 289
4
votes
1
answer
302
views
What are the languages produced by context free-grammars with backspace?
If we add backspace to the output alphabet, are all the languages produced still context-free? (If not, then what are they?)
The word (a, b, c, Backspace, Backspace), for example, gets interpreted as ...
- 181
1
vote
1
answer
73
views
Prove that the "6-rule" CFG for arithmetic expressions below is unambiguous
Question: Prove that the 6-rule CFG for arithmetic expressions below is unambiguous.
The CFG is as follows. $G = (V:=\{E,T,F\}, \Sigma:=\{+, \times,(,),x\},R,E\})$
where $R$ consists of 6 rules:
$E\...
0
votes
1
answer
468
views
Prove that the grammar $S\rightarrow (S)|SS|\epsilon$ generates precisely all well-balances parentheses
Question: prove that the grammar $G = (\{S\}, \{(,)\}, R, S)$ where $R$ consists of three rules:
$S \rightarrow (S)~|~SS~|~\epsilon$
generates precisely all well-balanced parentheses.
I found a source ...
1
vote
1
answer
421
views
Prove a subset of a regular language is regular, context-free but not regular or not context free
I've been tasked with solving this problem, but I'm not sure where to begin:
Let $L$ be a context-free language. $L'$ contains all the words that belong to $L$ which can't be defined as $z=uvwxy$, ...
- 113
-1
votes
2
answers
71
views
Is this a context free language? I need to make PDA but I don't think it is doable
I got a question:
Design a pushdown automata that can recognize strings in L= {$ a^n b^{2n} c^{3n} | n ≥ 0 $} .
I tried to think and design it, but I couldn't find it. The best that I can think of is ...
- 1
-2
votes
1
answer
55
views
How to use Pumping Lemma $L = \{ wsw \mid w \in \{0,1\}^*, s \in \{2\}^* \text{, and } |w| = 2 \cdot |s| \}$?
I'm trying to use the Pumping Lemma to prove that $L = \{ wsw \mid w \in \{0,1\}^*,\ s \in \{2\}^*\text{ and } |w| = 2\cdot|s| \}$ is not a CFL.
-2
votes
1
answer
64
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 ...
- 47
1
vote
1
answer
207
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 ...
- 111
1
vote
3
answers
413
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, ...
- 239
1
vote
1
answer
66
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?
- 47
-2
votes
1
answer
63
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 ...
- 239
1
vote
1
answer
125
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 ...
- 47
0
votes
0
answers
38
views
Regular, CFL, non-CFL infinite closures [duplicate]
I was wondering about infinite closure properties.
Are the Regular languages closed under infinite union? Infinite intersection?
Probably not, by taking $\forall n>0~~L_n=\{a^nb^n\}\in RL$, then $\...
- 239
3
votes
4
answers
2k
views
Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?
Why is $L=\{w \mid ~|w|\bmod3=\#_a(w)\bmod3\}$ a regular language?
$\#_a(w)$ is the number of $a$'s in $w$.
So far every language that I saw containing modulo was a ...
- 239
0
votes
0
answers
36
views
How to show that $\{a^p ~|~ p\text{ is not prime}\}$ is not a CFL? [duplicate]
I want to show that the language $L=\{a^p ~|~ p\text{ is not prime}\}$ is not a CFL.
If I look at $\bar{L}=\{a^p ~|~ p\text{ is prime}\}$, it is pretty straightforward to show that it is not a CFL ...
- 239
2
votes
1
answer
43
views
Why is $L=\{w~|~\#_a(w) \ge \#_b(w)\}○\{w~|~\#_a(w) \le \#_b(w)\}$ regular?
Why is this language regular: $L=\{w~|~\#_a(w) \ge \#_b(w)\}○\{w~|~\#_a(w) \le \#_b(w)\}$?
Where $\#_a(w)$ is defined as the number of $a$ in $w$.
Isn't that a concatenation between 2 CFL?
Thanks!
- 239
1
vote
1
answer
70
views
is there a non-context free language A such that A1 is context free?
Is there a non-context free language A over the alphabet $\{0,1\}$ such that $A1 := \{a1 : a\in A\}$ is context free?
I was thinking of the language $A = \{0^n 1^{n-1} : n > 0\}.$ Unfortunately, ...
- 289
1
vote
1
answer
71
views
Is $\{x2y : |x| = |y|, x\in A, y\in\{0,1\}^*, d(x,y) = k\}$ context-free for some infinite regular language $A$?
For two equal-length binary strings $x$ and $y$, let $d(x,y)$ denote the Hamming distance. Prove or disprove: there exists a positive integer $k$ such that the language $\{x2y : |x| = |y|, x\in A, y\...
- 289
0
votes
1
answer
92
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 ...
- 289
0
votes
3
answers
398
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
1
answer
58
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$...
- 239
1
vote
3
answers
2k
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 ...
- 239
4
votes
1
answer
107
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&...
- 43
1
vote
2
answers
171
views
Prove or disprove that the language $L = \{xcy\, | \, x,y\in \{a,b,c\}^\star, |x|_a = |y|_b \}$ is context free
Let me cross post my question from math.stackexchange, since I feel this community is more related to the field.
Title is self explanatory. I want to know is the language $L = \{xcy \,| \,x,y\in \{a,b,...
- 121
0
votes
2
answers
107
views
CFL with regular substitution to make a regular language
If I have a CFL, can I define a regular substitution to make it a RL?
For example, if I have the language $\{a^nb^n \mid n\ge0\}:$
Define $h(a)=a$ , $h(b)=b$, then $h(L)={a^*}$ , am I right?
Thanks!
- 1
-1
votes
1
answer
76
views
prove $A$ is context-free
Prove that the following language is context-free by giving a context-free grammar that generates the language: $A = \{a \in \{0,1\}^* : \text{ no character in an even position is a 0 or no character ...
- 289
-1
votes
1
answer
384
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 ...
- 167
1
vote
1
answer
262
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 ...
- 167
0
votes
1
answer
279
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 -> ...
-4
votes
1
answer
42
views
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 ...
-2
votes
2
answers
121
views
Context free grammar for $a^i b^j a^j b^i$
I recently started learning context free grammars and was working on a couple of exercise problems and couldn't really figure out how would this exactly look like.
I started with:
$$\begin{align}S&...
- 1
0
votes
1
answer
46
views
Determine the type of $L=\{w:|w|\text{ is even, and it has }\frac{|w|}2\text{ consecutive 0's}\}$
I've been solving a lot of questions lately about determining the type of a given language, by type I mean whether it's regular, CFL, in P, Turing-decidable, Turing-acceptable, or all the languages. ...
- 453
2
votes
0
answers
76
views
Is the language $L = \{{a^{2n+1}b^{m+2}a^n | m \neq 2n}\}$ context-free?
$L = \{{a^{2n+1}b^{m+2}a^n | m \neq 2n}\}$
I tried to split $L$ in 2: when $m > 2n$ and $m<2n$, however both resulting languages are not context-free, so I did not find out anything about $L$.
...
-3
votes
1
answer
266
views
Prove a stronger version of the pumping lemma for context-free languages
Let $L$ be a context-free language. Prove that there exists integer $p>0$ such that
$ \forall z\in L $ such that $ |z|\ge p $, there exists a partition $ z=uvwxy $ such that
$|vwx|\le p$
$|vx|\...
- 121
2
votes
1
answer
151
views
Is $\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j ;\ j \text{ is even, then } k =i+j\}$ context-free?
$L=\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j
;\ j \text{ is even, then } k =i+j\}$
I tried writing $L$ as the union of the language created with $j$ odd and the one with $j$ even.
When $j$ is ...
- 21
0
votes
2
answers
245
views
Design a CFG for $L=\{ w \in \{ 0,1 \}^* \}$, where $w$ contains at least three ones
$L=\{ w \in \{ 0,1 \} \}$ where $w$ contains at least three ones
Here is one solution for the productions:
$S \to A1A1A1A$
$A \to 1A | 0A | \epsilon$
However, now I have a question. Could I modify the ...
- 167
1
vote
1
answer
109
views
How to create all even length words from a given CNF grammar
given CFG G1 = {V1, Σ1, R1, S1} in its CNF form,
I have to define a new G5 grammar that constructs L(G5) using {V1, Σ1, R1, S1}:
while L(G5) = { x ∈ L(G1) | |x| is even }
i . e .
L(G5) composed of all ...
- 11
0
votes
1
answer
146
views
Context-free grammar for language $L = \{u \in \{a, b\}^* \mid |u|_a = |u|_b\}$ [duplicate]
I need to find the production rules for the following language:
$L = \{u \in \{a, b\}^* \mid |u|_a = |u|_b\}$
Well, the first thing I could come up with is
$S \to aSb | \epsilon$
But this only covers ...
- 167
0
votes
0
answers
94
views
Union of two context-free grammars and their productions
Is it possible to create an union of two context-free grammars? I found a PDF material from the university of Iowa where they claim that it's possible but I just don't know how. They had that for ...
- 167