Questions tagged [context-free]

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

1776 questions
101
votes
5 answers

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. How do I show the opposite, though? My TA has…
Raphael
  • 73,461
  • 31
  • 185
  • 415
54
votes
1 answer

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's the question: Show that the language $L = \{xy…
Dave Clarke
  • 20,375
  • 4
  • 72
  • 114
37
votes
2 answers

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 sensitive grammar" but I still failed to find what the…
CodyBugstein
  • 3,035
  • 11
  • 34
  • 47
36
votes
4 answers

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 } S$$ and make this to an unambiguous grammar, I…
user1594
  • 561
  • 2
  • 6
  • 9
30
votes
4 answers

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 with this ?
Shady Atef
  • 411
  • 5
  • 7
30
votes
2 answers

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 a context-free grammar for the language. Are there…
D.W.
  • 170,893
  • 23
  • 241
  • 528
26
votes
4 answers

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've tried to intersect $L$ with $a^*b^*a^*b^*$, but…
Evgeny Eltishev
  • 771
  • 1
  • 6
  • 8
26
votes
3 answers

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 described as the concatenation of two words of the same…
Robert777
  • 747
  • 6
  • 15
25
votes
1 answer

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 Automaton D that accepts exactly the language G accepts…
Andrew Tomazos
  • 759
  • 1
  • 7
  • 15
22
votes
3 answers

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 first and last levels 1 (regular languages and…
Luke Mathieson
  • 18,471
  • 4
  • 62
  • 87
22
votes
6 answers

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 \mathbb{N}\}$), test whether the language is…
D.W.
  • 170,893
  • 23
  • 241
  • 528
21
votes
1 answer

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 free but not regular. The language generated by…
sanjeev mk
  • 419
  • 1
  • 3
  • 7
20
votes
2 answers

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 complement(!?) Here is my argument. Each CF language $L$…
Hendrik Jan
  • 31,677
  • 1
  • 55
  • 110
19
votes
2 answers

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 $C\to cC$ will loop forever and never generate a…
cmtjk
  • 293
  • 2
  • 5
19
votes
1 answer

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. However, if both $G_1$ and $G_2$ are left-linear (or…
user51117
1
2 3
…
99 100