Questions tagged [context-free]
Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.
238
questions
98
votes
5
answers
103k
views
How to prove that a language is not context-free?
We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free....
- 72k
28
votes
2
answers
46k
views
How to prove that a language is context-free?
There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free?
What techniques are there to prove this? Obviously, one way is to exhibit ...
D.W.♦
- 156k
53
votes
1
answer
24k
views
Show that { xy ∣ |x| = |y|, x ≠ y } is context-free
I remember coming across the following question about a language that supposedly is context-free, but I was unable to find a proof of the fact. Have I perhaps misremembered the question?
Anyway, here'...
- 20.2k
32
votes
4
answers
31k
views
How to prove that a grammar is unambiguous?
My problem is how can I prove that a grammar is unambiguous?
I have the following grammar:
$$S
→ statement
∣ \mbox{if } expression \mbox{ then } S
∣ \mbox{if } expression \mbox{ then } S \mbox{ else } ...
- 521
8
votes
3
answers
4k
views
Context-free grammar for $L = \{a^{2^k}, k \in\mathbb{N}\}$
In an exercise, I am asked to find a context free grammar for language $L = \{a^{2^k}, k \in \mathbb{N}\}$.
I have been trying to use a "doubling" variable. If $a^{2n} \in L, n\in\mathbb{N}$ then use ...
- 215
6
votes
2
answers
9k
views
Converting to CFG from a CFL? [duplicate]
I am trying to learn CFG. Now to make a CFG from a CFL it is really difficult for me.
Is there any simple rule or steps so that I can easily find a CFG for a CFL. I am trying to solve one problem ...
- 173
8
votes
2
answers
25k
views
Context Free Grammar for {a^ib^j | i,j ≥ 0; i ≠ 2j}
Can someone help with this:
$L=\{a^ib^j \mid i,j \ge 0 \text{ and } i \ne 2j\}$
I'm trying to write a grammar for this language?
I don't know how to do this.
I tried this:
$S \rightarrow aaAb \...
- 115
10
votes
3
answers
3k
views
If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?
I'm am stuck solving the next exercise:
Argue that if $L$ is context-free and $R$ is regular, then $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} $ (i.e. the right quotient) is context-...
- 201
5
votes
2
answers
47k
views
How to convert PDA to CFG
I learned how to convert context-free grammar to pushdown automata but how can I do the opposite? to convert PDA to CFG?
For example: to write CFG for the automata
My attempt:
$S=A_{03}$ because $...
- 449
20
votes
1
answer
35k
views
Intersection of context free with regular languages
The intersection of a context free language L with a regular language M, is said to be always context free. I understood the cross product construction proof, but I still don't get why it is context ...
- 399
18
votes
3
answers
9k
views
Example of a non-context free language that nonetheless CAN be pumped?
So basically L satisfies the conditions of the pumping lemma for CFL's but is not a CFL (that is possible according to the definition of the lemma).
- 183
10
votes
1
answer
641
views
How can ws with |w| = |s| and w ≠ s be context-free while w#s is not?
Why does (if so) the seperator $\#$ is making a difference between the two languages ?
Let say:
$L=\{ws : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \}$
$L_{\#}=\{w\#s : |w|=|s|\, w,s\in \{0,1\}^{*}, ...
- 256
10
votes
5
answers
1k
views
Language of the values of an affine function
Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let $a$ and $b$ be integers, with $a > 0$. Consider the language of the decimal expansions ...
8
votes
3
answers
7k
views
Proving that any CF language over a 1 letter alphabet is regular
I would like to prove that any context free language over a 1 letter alphabet is regular. I understand there is Parikh's theorem but I want to prove this using the work I have done so far:
Let $L$ be ...
- 219
8
votes
1
answer
4k
views
prove no DPDA accepts language of even-lengthed palindromes
How do you prove that the language of even-lengthed palindromes, i.e.,
$L=\left\{ ww^R \mid w\in \left\lbrace 0,1 \right\}^* \right\}$, can not be accepted by a determinsitc Push-Down-Automaton?
Is ...
- 991
17
votes
1
answer
11k
views
Construct a PDA for the complement of $a^nb^nc^n$
I am wondering if this is even possible, since $\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL}$. Therefore a PDA that can distinguish a word $w\in\{a^n b^n c^n \mid n \geq 0\}$ from the rest of $...
- 305
12
votes
3
answers
8k
views
Easy proof for context-free languages being closed under cyclic shift
The cyclic shift (also called rotation or conjugation) of a language $L$ is defined as $\{ yx \mid xy \in L \}$. According to wikipedia (and here) the context-free languages are closed under this ...
- 29.8k
7
votes
3
answers
21k
views
Regular Expression to Context-Free Grammar
Anyone knows if there is an algorithm for directly write the context-free grammar that generates a given regular expression?
- 173
5
votes
2
answers
2k
views
Pumping lemma: if you can keep pumping, what does this tell you?
Hypothetically, let's say you are using the pumping lemma for either regular or context free languages. Now using either, you come across a case that remains true despite pumping it. In this situation,...
- 51
4
votes
3
answers
9k
views
Find a pushdown automaton for { x#y ∣ x ≠ y }
I was told to built a PDA that recognizes the following language:
$$L = \{x\#y \mid x,y \in \{0,1\}^{\ast} \wedge x \neq y\}$$
My attempt is basically to push $x$ to the stack for every $1$ and $0$ ...
- 51
3
votes
1
answer
2k
views
Context Free Grammar for language L
Can someone help with this:
$L=\{a^ib^j \mid i,j \ge 1 \text{ and } i \ne j \text{ and } i<2j\}$
I'm trying to write a grammar for this language?
I tried this:
$S \to S_1 \mid S_2 \\
S_1 \to aXb ...
- 115
25
votes
2
answers
29k
views
Is the complement of { ww | ... } context-free?
Define the language $L$ as $L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$. In other words, $L$ contains the words that cannot be expressed as some word repeated twice. Is $L$ context-free or not?
I'...
- 741
20
votes
2
answers
2k
views
Are context-free languages in $a^*b^*$ closed under complement?
The context-free languages are not closed under complement, we know that.
As far as I understand, context-free languages that are a subset of $a^*b^*$ for some letters $a,b$ are closed under ...
- 29.8k
12
votes
1
answer
5k
views
Is an infinite union of context-free languages always context-free?
Let $L_1$, $L_2$, $L_3$, $\dots$ be an infinite sequence of context-free languages, each of
which is defined over a common alphabet $Σ$. Let $L$ be the infinite union of $L_1$, $L_2$, $L_3$, $\dots $;
i....
- 2,193
12
votes
1
answer
3k
views
A pumping lemma for deterministic context-free languages?
The pumping lemma for regular languages can be used to prove that certain languages are not regular, and the pumping lemma for context-free languages (along with Ogden's lemma) can be used to prove ...
- 9,037
8
votes
2
answers
716
views
What's the reason for the second condition of the pumping lemma(s)?
For a language $L$ with pumping length $p$, and a string $s\in L$, the pumping lemmas are as follows:
Regular version:
If $|s| \geq p$, then $s$ can be written as $xyz$, satisfying the following ...
- 1,287
7
votes
3
answers
438
views
First half of context-free palindromes
If $L\subseteq\Sigma^*$ is a regular language, then $\text{mir}(L) = \{ww^R \mid w\in L\}$ is context-free. This is a nice exercise.
Question: does the reverse hold? Thus, if $\text{mir}(L)$ is ...
- 29.8k
4
votes
2
answers
336
views
Context free grammar construction
My problem with CFG is, I am to generally create ones that don't have requirements such as:
$\qquad \{a^m b^n \mid m \le n \le 2m \}$
I have no clue where to begin, and how to approach it. I was ...
CSTHEORY
3
votes
3
answers
3k
views
Why DCFL is not closed under kleene star?
I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example
user52152
3
votes
2
answers
41k
views
Is $a^n b^n c^n$ context-free? [duplicate]
I am new to grammars and I want to learn context free grammars which are the base of programming languages. After solving some problems, I encountered the language
$$\{a^nb^nc^n\mid n\geq 1\}\,.$$
...
- 156
3
votes
1
answer
363
views
Is the language of words with as many a's in the first as b's in the second part context-free?
Is $L = \{ W_1W_2 \mid W_1,W_2 \in (a+b)^* , N_a(W_1) = N_b(W_2)\}$ context free? Can we construct an NPDA for the language?
There is a book here that claims $L$ is not CF (without any elaboration), ...
- 131
2
votes
1
answer
912
views
PDA for $\{a^nb^m \mid 0 < n \le m \le 3n\}$
I have to design a PDA that recognizes the language $\{a^nb^m \mid 0<n\leq m\leq3n\}$
I tried to partition the stack into 3 partitions with the first partition being the size of $n$ with character ...
- 135
0
votes
2
answers
863
views
How do we check $x ≠ y$ in $PDA$ for $L = \{xy | x, y \in (0 + 1)^*, |x| = |y|, x ≠ y\}?$
We know that $L
= \{ xy | x, y \in (0 + 1)^*, |x| = |y|,
x≠y\}$
is context free. But my question is how we check $x ≠ y$ in $PDA?$ For example $x=0^n1^n$ and $y=1^{2n}.$ We can easily draw $PDA$ by ...
- 346
19
votes
1
answer
2k
views
Is language equality for linear context-free grammars decidable?
Let's consider two context-free grammars $G_1$ and $G_2$ and ask the following question: Is $L(G_1) = L(G_2)$, that is, are the two grammars equivalent?
In general, this problem is undecidable. ...
user51117
16
votes
2
answers
2k
views
Decidablity of Languages of Grammars and Automata
Note this is a question related to study in a CS course at a university, it is NOT homework and can be found here under Fall 2011 exam2.
Here are the two questions I'm looking at from a past exam. ...
- 1,115
14
votes
2
answers
13k
views
Are all context-free and regular languages efficiently decidable?
I came across this figure which shows that context-free and regular languages are (proper) subsets of efficient problems (supposedly $\mathrm{P}$). I perfectly understand that efficient problems are a ...
- 2,193
12
votes
2
answers
20k
views
Examples of context-free languages with a non-context-free complements
Context-free languages are not closed under complementation. In the lectures we have been given the same argument as here on Wikipedia: For
$$A = \{\mathtt a^n \mathtt b^n \mathtt c^m;~m, n ∈ ℕ_0\}\...
- 383
11
votes
2
answers
6k
views
How can I prove this language is not context-free?
I have the following language
$\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$
I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a context-...
- 435
8
votes
1
answer
5k
views
Are DCFLs closed under reversal?
According to this chart, DCFLs are closed under reversal.
However, I am not convinced as the intuitive proof (reversing the arrows of the controlling finite state machine and switching the pushes and ...
- 259
7
votes
4
answers
542
views
Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?
How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language.
$A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$, where $x^R$ is the ...
- 1,697
7
votes
2
answers
1k
views
Do NPDA work in parallel?
Assume my language is
$$
L= ww^{r}\
$$
Now when we use NPDA for this,we will guess middle every time. It may be actual middle or it may not, so a new branch is created every time as I have a choice ...
- 431
6
votes
2
answers
3k
views
Designing a PDA w/o $\epsilon$-moves and $\leq 2$ states to accept an $\epsilon$-free CFL by final state
I understand that any CFL can be accepted by a PDA by final state or empty store but I have been rather stumped by this question.
The question states that the PDA has at most 2 states. Clearly 1 will ...
- 163
6
votes
1
answer
6k
views
A non-regular language satisfying the pumping lemma
I got a problem to solve, which is to demostrate that the language $L$, given by:
$L = \{ab^nc^n\mid n \geq 0\} \cup \{a^kw \mid k\geq 2 \wedge w \in \Sigma^*\}$
Satisfies the pumping lemma.
Is not ...
- 171
5
votes
1
answer
2k
views
How to prove the emptiness of intersection of two context free languages is undecidable?
Where can I find a proof that the emptiness problem for the intersection of two context free languages is undecidable? I searched on the internet but could not find anything helpful.
Do you maybe ...
- 385
5
votes
1
answer
657
views
Inducing a context free grammar [closed]
I have a file containing a subset of possible strings from a context free language. I am looking for a mechanism to induce the grammar from this information. Is that possible?
- 153
3
votes
1
answer
709
views
Is the language of all ucv with u ≠ v context-free?
Is $L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^* , w_1 \neq w_2 \}$ a CFL?
In my opinion it is not since if we want to know the inequality of $w_1$ and $w_2$ we must be aware of their equality and that is ...
- 41
3
votes
2
answers
254
views
Using pumping lemma to show a language is not context free(Complicated)
How can i show that the following long language is not context free using the pumping lemma?
$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}...
- 95
3
votes
1
answer
8k
views
Pushdown automaton for complement of { ww | ... }
I want to be able to describe the idea behind the pushdown automaton (no tables or diagrams).
So, I already know that $L = \{ ww \mid w \text{ in } (0,1)^*\}$ is not context free. Since CFL are not ...
2
votes
1
answer
2k
views
Prove that regular languages and context-free languages aren't closed under $Perm(L)$
Let the operation $$Perm(L) = \{ w | \exists u \in L \text{ such that } u \text{ is a permutation of } w \}$$
Prove that both regular languages and CFLs aren't closed under $Perm(L)$.
I've tried ...
- 379
2
votes
2
answers
18k
views
How to construct Context Free Grammar of words with equal number of 0's and 1's [duplicate]
i am trying to find a cfg for this cfl
L = $\{ w \mid w \text{ has an equal number of 0's and 1's} \}$
is there a way to count the number of 0's or 1's in the string?
- 41