Questions tagged [context-free]

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

Filter by
Sorted by
Tagged with
89
votes
5answers
64k 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....
26
votes
2answers
25k 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 ...
43
votes
1answer
12k 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'...
25
votes
4answers
21k 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 } ...
7
votes
2answers
5k 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 ...
7
votes
2answers
11k 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 \...
15
votes
3answers
6k 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).
10
votes
5answers
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 ...
9
votes
3answers
2k 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-...
15
votes
1answer
21k 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 ...
16
votes
1answer
8k 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 $...
9
votes
1answer
301 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\}^{*}, ...
5
votes
2answers
923 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,...
6
votes
3answers
1k 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 ...
7
votes
3answers
3k 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 ...
3
votes
2answers
4k 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$ ...
2
votes
1answer
1k 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 ...
2
votes
2answers
20k 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 $...
13
votes
2answers
14k 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'...
20
votes
2answers
1k 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 ...
12
votes
2answers
9k 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 ...
19
votes
1answer
1k 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. ...
8
votes
1answer
3k 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 ...
7
votes
1answer
2k 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 ...
5
votes
2answers
339 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 ...
11
votes
2answers
13k 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\}\...
10
votes
1answer
2k 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 ...
1
vote
1answer
5k 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 ...
0
votes
1answer
198 views

Example Context free grammar

Is there a nice way to give context free grammar for $$\{a^nb^ma^kb^l:n+m=k+l\}?$$ From PDA point of view it seems we just push + on stack if we see a, push + on stack if we see b, pop + from stack ...
16
votes
2answers
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. ...
11
votes
2answers
4k 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-...
5
votes
2answers
2k 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 ...
2
votes
1answer
582 views

Is this unambiguous grammar equivalent?

I have a simple context free grammar $(\{A\}, \{(,)\}, R, A)$, which consists of this one production rule: $A \rightarrow AA\, \vert\, (A)\, \vert\, \epsilon$ I believe this is ambiguous! For ...
2
votes
1answer
278 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 ...
2
votes
2answers
92 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\}...
6
votes
2answers
3k views

In context-free grammar (CFG), what is the importance of doing both leftmost and rightmost derivations?

I am a beginner learning theoretical computer science. While learning about CFG, I found that doing both leftmost and rightmost derivations gave me the same parse tree. So, my question is: Why is it ...
13
votes
3answers
1k 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 ...
8
votes
2answers
2k views

How do I show that whether a PDA accepts some string $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?

How do I show that the problem of deciding whether a PDA accepts some string of the form $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable? I have tried to reduce this problem to another undecidable ...
8
votes
1answer
460 views

Is this language Context-Free?

Is the language $$L = \{a,b\}^* \setminus \{(a^nb^n)^n\mid n \geq1 \}$$ context-free? I believe that the answer is that it is not a CFL, but I can't prove it by Ogden's lemma or Pumping lemma.
7
votes
3answers
15k 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?
22
votes
1answer
2k 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 ...
3
votes
2answers
5k views

Defining a context-free grammar for $\{w \in \{0, 1\}^* : \#_0(w) = \#_1(w)\}$ [duplicate]

I have a language where each string in the language has even amount of $0$'s as $1$'s (e.g., $0101$, $1010$, $1100$, $0011$, $10$ are all in the language). I was hoping to define a context-free ...
18
votes
2answers
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 $...
11
votes
3answers
4k 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 ...
9
votes
1answer
22k views

Convert CFG to PDA

Is there any set of rules or methods to convert any context free grammar to a push down automata? I already found some slides online but I wasn't able to understand them. In slide 10 he speaks ...
9
votes
2answers
9k views

Two-State Turing Machine for Parenthesis Matching

In college we have been learning about theory of computation in general and Turing machines more specifically. One of the great theoretical results is that at the cost of a potentially large alphabet (...
5
votes
2answers
4k views

complexity of determining whether a language given by context free grammar is empty

I know that it is decidable problem to check whether given context free grammar represents empty language -- for instance, AFAIR one could convert it to Chomsky normal form, and then check if any word ...
14
votes
2answers
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 ...
11
votes
2answers
8k 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 \...
6
votes
3answers
152 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 ...