Questions tagged [context-free]
Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.
1,687
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
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
37
votes
2
answers
5k
views
What does "context" in "context-free grammar" refer to?
There are lots of definitions online about what a Context-Free Grammar is, but nothing I find is satisfying my primary trouble:
What context is it free of?
To investigate, I Googled "context ...
- 2,957
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
29
votes
3
answers
3k
views
What's really meant by context-free in the term context-free grammar?
I have been studying compilers for a while, and I have been searching what's meant by "context" in grammar and what it means for grammar to be "context-free", but with no result.
So can anyone help ...
- 401
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
26
votes
3
answers
2k
views
Is the language of pairs of words of equal length whose hamming distance is 2 or greater context-free?
Is the following language context free?
$$L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} $$
As pointed out by sdcvvc, a word in this language can also be ...
- 747
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
24
votes
1
answer
4k
views
Decide whether a context-free languages can be accepted by a deterministic pushdown automaton
Given a context-free grammar G, there exists a Nondeterministic Pushdown Automaton N that accepts exactly the language G accepts. (and visa versa)
There may also exist a Deterministic Pushdown ...
- 709
22
votes
3
answers
586
views
Machines for context-free languages which gain no extra power from nondeterminism
When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines.
For the ...
- 18.1k
22
votes
6
answers
2k
views
Algorithm to test whether a language specified in algebraic form is context-free
Is there an algorithm/systematic procedure to test whether a language is context-free?
In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \...
D.W.♦
- 156k
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
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.9k
19
votes
2
answers
2k
views
Can there be 'dead states' in a context-free grammar?
Can a context-free grammar include "dead states" from an automaton, such as
$$G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\}, A\big)\,?$$
The production rules $B\to C$ and $...
- 293
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
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
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
17
votes
2
answers
4k
views
Removing left-recursion in grammar while maintaining left-association of operator
I have a problem with this exercise:
Let G be the following ambiguous grammar for the λ-calculus:
E → v | λv.E | EE | (E)
where E is the single non-...
- 173
16
votes
3
answers
2k
views
What would you get if you add parameters to context free grammars?
I was thinking of grammars for indendation-sensitive languages and it looks like CF grammars would do the trick if combined with parameters. As an example, consider this fragment for simplified Python ...
- 285
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
15
votes
5
answers
6k
views
How is non-ambuiguity different from determinism?
I am trying to understand what is meant by "deterministic" in expressions such as "deterministic context-free grammar". (There are more deterministic "things" in this field). I would appreciate an ...
- 1,388
15
votes
2
answers
1k
views
Are the Before and After sets for context-free grammars always context-free?
Let $G$ be a context-free grammar. A string of terminals and nonterminals of $G$ is said to be a sentential form of $G$ if you can obtain it by applying productions of $G$ zero or more times to the ...
- 9,036
15
votes
2
answers
823
views
Is the language of words that are unbalanced in the first half context-free?
(Practice exam question in computational models)
Definition: A word $w\in \{0,1\}^*$ is called balanced if it contains the same number of $0$s as $1$s.
Let $L = \{w\in \{0,1\}^*\mid |w|$ is even and ...
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
13
votes
3
answers
16k
views
The importance of normal forms like Chomsky normal form for CFGs
I understand that context-free grammars can be used to represent context-free languages.It might have ambiguities. We also have normal forms like Chomsky and Greibach normal form. I couldn't ...
- 2,181
13
votes
1
answer
7k
views
Is there a context free, non-regular language $L$, for which $L^*$ is regular?
I know that there are non-regular languages, so that $L^*$ is regular, but all examples I can find are context-sensitive but not context free.
In case there are none how do you prove it?
- 583
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
12
votes
3
answers
23k
views
What is complement of Context-free languages?
I need to know what class of CFL is closed under i.e. what set is complement of CFL.
I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I ...
- 123
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
2
answers
559
views
What is the closure of context-free languages under finite intersections?
Famously the intersection of context-free languages need not be context-free. On the other hand the intersection of context-sensitive languages is context-sensitive.
So this leads to the question: ...
- 121
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.9k
12
votes
4
answers
7k
views
Is Python a context-free language?
From Wikipedia: Off-side_rule#Implementation, there is a statement:
...This requires that the lexer hold state, namely the current
indentation level, and thus can detect changes in indentation ...
- 285
12
votes
2
answers
11k
views
Finding the language generated by a context-free grammar
This is a question from the Dragon book (I apologize for translation mistakes, I don´t have the English version on hand):
What language is generated by this grammar?
$S \rightarrow a S b S \mid b S a ...
- 223
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
12
votes
2
answers
814
views
How much bigger can an LR(1) automaton for a language be than the corresponding LR(0) automaton?
In an LR(0) parser, each state consists of a collection of LR(0) items, which are productions annotated with a position. In an LR(1) parser, each state consists of a collection of LR(1) items, which ...
- 9,037
11
votes
2
answers
19k
views
Why are CFLs not closed under intersection?
I'm struggling with understanding how context free languages can be closed under union but are not closed under intersection. I was wondering if there was a simple proof or example demonstrating that ...
- 119
11
votes
4
answers
10k
views
Recursive descent parser with backtracking for the grammar $S \rightarrow aSa\ |\ aa$
Can someone enlighten me why a recursive descent parser with backtracking that tries the productions $S \rightarrow aSa$ and $S \rightarrow aa$ (in that order) does not recognize the language formed ...
- 143
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
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 ...
10
votes
2
answers
11k
views
Is it decidable whether a given context free grammar generates an infinite number of strings?
Is the decision problem "Does a given context free grammar generate an infinite number of strings" decidable? In order to test whether a context free grammar generates an infinite number of strings or ...
- 509
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
10
votes
1
answer
84k
views
Different between left-most and right-most derivation [duplicate]
I am a beginner started learning theoretical computer science. I just came through context-free grammars.
So my question is: what is the different between left-most and right-most derivation?
...
- 111
10
votes
1
answer
12k
views
Relation between simple and regular grammars
I am reading "An Introduction to Formal Languages and Automata" written by Peter Linz and after reading the first five chapters I face below problem with
simple and regular (especially right linear) ...
- 203
10
votes
2
answers
842
views
Language involving irrational number is not a CFL
I am working through a hard exercise in a textbook, and I just can't figure out how to proceed. Here is the problem. Suppose we have the language $L = \{a^ib^j: i \leq j \gamma, i\geq 0, j\geq 1\}$ ...
user101859
10
votes
1
answer
519
views
Constructing all context-free languages from a set of base languages and closure properties?
One way of looking at regular expressions is as a constructive proof of the following fact: it's possible to construct the regular languages by starting with a small set of languages and combining ...
- 9,037
10
votes
1
answer
1k
views
How do I reconstruct the forest of syntax trees from the Earley vector?
Using the Earley vector as a recognizer is quite straightforward: when the end of the string is reached, you just have to check for a completed axiomatic production started at position 0. If you have ...
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
1
answer
478
views
Given a string and a CFG, what characters can follow the string (in the sentential forms of the CFG)?
Let $\Sigma$ be the set of terminal and $N$ the set of non-terminal symbols of some context-free grammar $G$.
Say I have a string $a \in (\Sigma \cup N)^+$ such that $x a y \in \mathcal{S}(G)$ where $...
- 203
10
votes
1
answer
451
views
Shift-resolve parsing - questions
I've recently came across a paper describing the parsing technique
mentioned in the title. Unfortunately, the terminology used in said paper
is somewhat beyond my comprehension, so I've been ...
- 233
9
votes
3
answers
26k
views
Context-free Languages closed under Reversal
In class this week we've been learning about the CFLs and their closure properties. I've seen proofs for union, intersection and compliment but for reversal my lecturer just said its closed. I wanted ...
- 101