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
0
votes
2answers
19k views

How to take complement of a language?

I'm stuck on this question about context-free languages and was hoping for some clarification. $\qquad L = \{a^i b^j c^k \mid i=j, i=k\}$ is not context-free. Show that its complement is ...
2
votes
2answers
1k views

Is {xyx | |x|≥1} context-free?

Is $L=\{ xyx \mid x,y \in \{a,b\}^* \text {and } |x| \ge 1 \}$ context-free? If yes, please explain how we can write grammar or create a PDA for it. If not a CFL, then prove it through pumping ...
0
votes
1answer
214 views

Proving that $\{0^n 1^{n^2} \mid n \in \mathbb{N}\}$ is not context-free

How can I prove that $\{0^n 1^{n^2} \mid n \in \mathbb{N}\}$ is not a context free language? I tried to prove it using the pumping lemma, but I don't know how to deal with the case when $vxy$ ...
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 ...
26
votes
3answers
1k 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 ...
2
votes
1answer
718 views

Prove that context free languages are not closed under swapping prefixes and suffixes

Prove that context free languages aren't closed under this operation: $ A(L) = \{ zyx \mid x,y,z \in \{0,1 \}^*, xyz \in L \} $ Obviously, we need to find a context free language $L$ such that $A(L)$ ...
2
votes
2answers
3k views

Converting CFG to PDA

I have the following CFG, $S \rightarrow CB$ $C \rightarrow aCa \text{ }|\text{ } bCb \text{ }|\text{ } \text{#}B$ $B \rightarrow AB \text{ }|\text{ } \varepsilon$ $A \rightarrow a\text{ }|\text{ }b$ ...
3
votes
3answers
1k views

Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free?

Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free ? If we fix $n \in N$ then we know that the language $L = \{ a^ib^j \mid \ \forall \ 1 \le k \le n \ , \ \ j\neq ki \} $ is ...
2
votes
1answer
2k views

Is the intersection of two context free languages recursively enumerable?

I read a quotation attributed to Sheila Greibach that says that the intersection of two context free grammars is recursively enumerable. I could not, however, find a citation for this quotation (and ...
1
vote
1answer
61 views

Questions about an answer to a pumping lemma question for CFLs

In the answer to this question, I'm not understanding how the string is derived for a given $l$. For example, Case 1: $vx = a^i$ where $i > 0$. Choose $l = 2$ to get $a^{n+i} b^{n+1} c^{n+1} d^...
2
votes
0answers
180 views

The grammar of the GeoQuery language

GeoQuery is a dataset used for benchmarking semantic parsers. It contains 880 queries about USA geography. The queries are in Prolog format, for example: answer(A,longest(A,(river(A),traverse(A,B),...
3
votes
1answer
2k views

Are permutations of context-free languages context-free?

Given a context-free language $L$, define the language $p(L)$ as containing all permutations of strings in $L$ (i.e. all strings in $L$ such that the order of symbols is not important). Is $p(L)$ ...
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 ...
0
votes
2answers
178 views

Proving $\{xx^R \mid x\in L_1, x^R\in L_2\}$ is context-free

I have this problem: Let $L_1$ and $L_2$ be two regular languages. Show that $L_3 = \{xx^r : x \in L_1, x^r \in L_2 \}$ is a context-free language. I am unsure how to prove that some language is ...
8
votes
1answer
547 views

Is the language $\{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free?

Is the language $ L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free ? I guess that it's not context free because it seems too complicated for a PDA to decided whether 2 numbers ...
0
votes
0answers
22 views

Pumping Lemma on CFL Problem [duplicate]

I have laid out the various cases that would make this not a context free language already and proved all but one for this set: \begin{equation} A = \{a^f b^g \mid f = g^2\} \end{equation} ...
4
votes
1answer
4k views

How to find the pumping length of a context-free language?

Please help me understand, and if possible, tips, to determine a pumping length $p$. Suppose I have the example : Let $G$ be a Context-Free-Grammar with a set of variables $\{S,A,B,C\}$, set of ...
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 ...
5
votes
1answer
269 views

Closure under intersection of context free binary trees

Some sets of ordered binary trees can be represented as a CFG with rules of the form A -> aBC A -> b Where A,B,C are ...
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 ...
5
votes
2answers
350 views

Why is the following language not context-free?

$L = \{a^n b^m | m \not= n^2 \}$ I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck. Assuming that $ a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ ...
0
votes
1answer
2k views

CFG for $\{a^i b^j : 2 i<j\}$ [duplicate]

So I have a question: Give a CFG for $\{a^i b^j : 2 i<j\}$ And this is my approach: $S\to AB$ $A\to aAb\mid \varepsilon$ $B\to b \mid bB$ A confirmation, or correction, along with how you ...
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 (...
4
votes
2answers
6k views

Give CFG and PDA for the words that start and end with the same symbol

I need to give a PDA and CFG for a language that contains all binary strings that start and end with the same symbol. I've created the CFG with no problem, but I'm stuck with the PDA and don't quite ...
1
vote
1answer
763 views

How can I show a linear languages are closed against concatenating with regular ones?

This was given as a homework problem but I have already submitted the assignment. I'd like to resolve it at this point for my own satisfaction. Given that $L_1$ is a linear language and $L_2$ is a ...
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 ...
4
votes
2answers
228 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 ...
3
votes
1answer
2k views

CFG to CNF conversion steps

I could find that different texts follow different steps in the conversion of CFG to Chomsky Normal Form. I couldn't find any presumptions they made in the conversion steps. I have some questions ...
2
votes
2answers
1k views

Pumping lemma for CFG doubt

I was looking at the pumping lemma for CFG. I came across the first problem $a^nb^nc^n$ and understood the answer. Then I thought of the problem $a^nb^n$. I know that this is context free and thought ...
1
vote
2answers
275 views

How to write Context Free Grammar with numerical restrictions

I am supposed to write a Context free grammar that generates the language: $\qquad L(G) = \{0^{3n}1^{2n}0^{m}1^{m} : n \ge 1, m \ge 1\}$ I have the rules: $$S \rightarrow 000S$$ $$S \rightarrow ...
0
votes
1answer
156 views

How do you apply Context-Free Pumping Lemma to these problems, and how do the approaches differ? [closed]

How are these Context-Free Pumping Lemma Approaches differ? Maybe this might help understand pumping lemma better $(a^{i}b^{i}c^{j}d^{j} \mid i, j \geq 0$} $(a^{i}b^{j}c^{i}d^{j} \mid i, j \geq 0$} ...
3
votes
2answers
353 views

Why is the subset of palindromes of a regular language context-free?

Why is $A(L) = \{x \in L \mid x = x^R \}$ context-free if $L$ is a regular language? Trying to understand the approach to determining whether a regular language is context-free.
2
votes
1answer
2k views

Is $L= \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $ context free?

$L = \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $ Is this language a context free language? If yes give a PDA. If no, give a proof. The pumping lemma for context free languages doesn't seem to work ...
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 \...
3
votes
2answers
11k views

Grammar for describing boolean expressions with AND, OR and NOT

I wrote the following LL(1) grammar to describe the set of boolean expressions involving AND ,OR an ...
12
votes
3answers
11k 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 ...
1
vote
1answer
122 views

Is the following language context free?

Is $L = \{ a^nb^nc^j \mid n \le j\}$ a context-free language? I'm getting really stuck generating a grammar for it. Any help would be appreciated.
3
votes
1answer
247 views

Proving that a specific language is a CFL, and that another language is not a CFL

I have two languages $C_1$ and $C_2. \left(\Sigma=\{0,1\}\right)$: $C_1=\left\{xyz\mid x,z \in \Sigma^*, y \in \Sigma^*1\Sigma^*, \text{ where } |x|=|z| \geq |y|\right\}$, and $C_2=\left\{xyz\mid x,z ...
0
votes
1answer
131 views

Context free grammar for {a^mb^n | m ≠ n} [duplicate]

I need to find a context-free grammar for the above expression, $a^{m}b^{n}$ for the set $L = \left\{{a, b}\right\}$, but I am having difficulty accounting for the condition $m \neq n$. This is what ...
1
vote
1answer
4k views

CFG to Chomsky normal form

I've read this part like 3-4 times and I'm not understanding what is going on. Let G6 be the following CFG and convert it to Chomsky normal form by using the conversion procedure just given. The ...
2
votes
1answer
126 views

Context free grammar for $1^k0^{2k}$

I need a hint for writing a context-free grammar for the language $L=\{1^k0^{2k}:k\in \mathbb N\}$. I'm starting to doubt that it can be done for general $k$.
3
votes
1answer
276 views

Lookahead set: Determining minimum $k$ such that $G$ is a strong $LL(k)$ grammar

How do we determine minimum $k$ such that $G$ is a strong $LL(k)$ Grammar Like for grammar $G$ with the following rules $S\rightarrow aAcaa \mid bAbcc,A\rightarrow a \mid ab \mid \epsilon$
9
votes
1answer
120 views

Does the following transformation preserve context-freeness?

I encountered this problem involving manipulating a context-free language. Let $L$ be a context-free language. Define $L^{\#} = \{ x : x^i \in L$ for every $i=0,1,2,...\}$. Is $L^{\#}$ always context-...
2
votes
1answer
253 views

Is The Following Language Regular? [duplicate]

Let $L_{1}$ and $L_{2}$ be 2 languages over the same alphabet $\Sigma$. $$A(L_1,L_2)=\{x\in \Sigma^*|\exists y,z\in L_2\text{ such that } yxz\in L_1\}$$ Assume that $L_{1}$ is regular and $L_{2}$ ...
10
votes
1answer
311 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 ...
1
vote
1answer
595 views

Are there languages generated by linear grammar which aren't regular?

Are there languages generated by linear grammer which aren't regular?
-3
votes
1answer
133 views

Regular and context free languages

I need to determine if the following languages are regular / context free and to explain. Please help me with that. $$L_1 = \{ a^{i_{1}}b a^{i_{2}}b a^{i_{3}}b a^{i_{4}}b a^{i_{5}}b a^{i_{6}}b a^{i_{...
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 ...
3
votes
1answer
137 views

Prove that $\{0^n 1^{n\cdot m} : n,m \in \mathbb{N}\}$ is not context-free

This is a homework problem I have spent several hours on. A "hint" is given that we may use this fact: If $n,j,k \in \mathbb{N}$ satisfy $ n \geq 2$ and $1 \leq j+k \leq n$, then $n^2+j$ does not ...
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 \...