We’re rewarding the question askers & reputations are being recalculated! Read more.

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
664 views

Prove L to not context free using pumping lemma on language L

$L = \{0^i1^j0^i1^j|i,j \geq 0\}$ I've tried letting $s = 0^p1^p0^p1^p$. But not sure where to go from here. Help would be appreciated.
5
votes
3answers
10k views

Language of balanced parentheses; Biconditional proof about parentheses

Let L be language of balanced parentheses. (a) Prove If there are equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'s, then w is in L. (b) Prove If w is in L, then ...
1
vote
3answers
156 views

Determine whether two languages are context free

(1) $L_1 = \{a^ib^{i+j}c^j|i,j\geq 0\} $ (2) $L_2 = \{xy | x,y \in \{0,1\}^*, x \neq y, |x| = |y| \}$ I doubt that $L_1$ is CFL. I've been trying to go with the string $s$ = $a^pb^{2p}c^p$. Thus, we ...
2
votes
1answer
2k views

Use pumping lemma to show L is not context free

Show that L = $\{0^{2^n}| n\geq 0\}$ is not a context free language. Let string $s = 0^{2^p}$. Then we know we can write $s$ as $s = uvxyz$. I know that |vy| > 0 and $|vxy| \leq p$. So how do I ...
0
votes
2answers
163 views

Equivalence of Context-Free-Grammar and Context-Free-Grammar in CNF

Given any Context-Free-Grammar, $G$, and another in Chomsky Normal Form, $G_c$, how can we check if both $G$ and $G_c$ generate the same language? One of the trivial ways I know of is to convert $G$ ...
-2
votes
1answer
200 views

Prove that X/Y/Z is context-free

Given languages X, Y and Z, each with alphabet, define X/Y/Z as: X/Y/Z = { w ∈ Σ* | ∃u ∈ Y and ∃v ∈ Z; such that wuv ∈ X }. Prove that if X is context-...
0
votes
0answers
25 views

Given languages A,B and C, each with alphabet Σ, define A/B/C as: [duplicate]

Given languages A,B and C, each with alphabet Σ, define A/B/C as A/B/C = { w∈Σ* | ∃u ∈ B and ∃v ∈ C; such that wuv ∈ A }. Prove that if A is context-free, and B and C are regular, then A/B/C is ...
2
votes
2answers
296 views

Does this language have a context-free grammar?

Here is a question that I encountered in one of my exams: Find one context-free grammar that recognizes the language: $\qquad L = \{a^n(b^mc^m)^pd^n \mid m, n, p \geq 0\} $ Can you find such a ...
0
votes
1answer
499 views

How do I prove that Context Free languages have more memory than FSM [closed]

This is very much clear to me that an FSM has limited memory (sufficient to store present state). How do I prove that (intutively or otherwise) that a CFL has more memory than a DFA or NFA (thus ...
1
vote
1answer
69 views

Concatenation among different language types

I am trying to figure out the result of the concatenation among different language types (regular, context free, ...). I think the result strongly depends on the nature of the languages which will be ...
1
vote
3answers
207 views

Deciding if language is Context-Free

I need help with deciding if $L$ is context-free. $$L = \{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s > t\}$$ Can be rewritten into: $$L = \{a^pb^qb^rc^sd^qd^te^pe^r \mid p, q, r, s \...
1
vote
2answers
107 views

Grammar to Language

Having: $\qquad \begin{align} S &\to aT \\ T &\to a \mid UTV \\ U &\to ab \mid ba \\ V &\to ac \mid ca \end{align}$ What language would be generated by this? How ...
2
votes
0answers
180 views

Constructing a Context Free Grammar for checking non-equality of strings [duplicate]

I have been studying the book Introduction to Computation by Michael Sipser on my own, and I'm stuck on this exercise from the chapter on Pushdown Automato and Context-Free Languages. The exercise is ...
4
votes
3answers
4k views

Is the language that accepts strings concatenated with their reverse regular?

If the set of regular languages is closed under the concatenation operation and is also closed under the reverse operation ($x^R$ is the reverse of $x$) then is the language generated by $$\{ww^R|w\in\...
0
votes
1answer
371 views

Determine if two grammars for the same language are ambiguous

I'm reading the book: Formal Syntax and Semantics of Programming Languages. I don't understand this exercise: Consider the following two grammars, each of which generates strings of correctly ...
0
votes
2answers
5k views

Prove Context Free languages not closed under difference?

Given two context-free languages $L_1$ and $L_2$, the language given by the difference of the two languages, $L_1 - L_2$, is (in general) not context-free. Is it possible to prove this without using ...
2
votes
2answers
2k views

Are regular and context free languages closed against making them prefix-free?

For a language L we define: $\qquad A(L) = \{ x \in L \mid \text{ no proper prefix of x is in L} \} $ Are regular / context free languages closed under this operation ? For regular languages I ...
1
vote
0answers
5k views

Context Free Grammar for $\{A^nB^nC^n | n \in \mathbb{N}\}$ [duplicate]

Is $L = \{A^n B^n C^n \mid n \in \mathbb{N}\}$ a context-free language, e.g. $AAAABBBBCCCC \in L$ If so, what's that context-free grammar that produces it?
1
vote
3answers
168 views

How can I produce a summation function from this set of production rules for a grammar?

I am not entirely sure if the title is the correct way to phrase what is occurring. There is a recurring process which I decided to attempt to model using production rules similar to those used in a ...
2
votes
1answer
4k views

Does the empty language have a CFG in CNF?

I just not sure does empty set have a context-free grammar in Chomsky normal form? That is, for $B=\emptyset$, then a context-free grammar is $S \to S$, I think which doesn't have a Chomsky normal ...
2
votes
2answers
103 views

I'm lookin for a method to construct a particular grammar?

I'm looking for an algorithm to construct a grammar which, given a set of words which can have multiple identical symbols, represents a compressed version of this set, that is, I can generate only the ...
0
votes
1answer
750 views

Removing identical variables in CFG Unit Productions

Productions of the form A-> A are removed immediately, but what if the production is of the form A -> AA? example: A -> AA | a
8
votes
2answers
558 views

Myhill-Nerode style characterization of CFL?

Define the Nerode equivalence over a language $L \subseteq \Sigma^{*}$ as $u \sim_L v$ iff $uw \in L \Leftrightarrow vw \in L$ for every $w \in \Sigma^{*}$. The Nerode equivalence ${\sim}_L$ has ...
1
vote
1answer
77 views

Is CFL closed against exchanging complementation and reversal?

Let $L$ be a language such that $\overline{L}^R$ (the reversal of the complement of $L$) is context-free. Is then also $\overline{(L^R)} \in \mathrm{CFL}$?
2
votes
2answers
205 views

Proving that CFLs are closed under even-ness using grammars

This is a question from a 2007 exam paper for a course I'm studying, question 2 on page 2. Theorem: Let $L$ be a context-free language. Let $L_{even}$ be the subset of $L$ consisting of all the ...
0
votes
1answer
2k views

Multiple-Choice Questions about decidability

I'm working on old MC-Questions about decidability und don't have the answers to the following ones: 1.) $L_1$ and $L_2$ are not decidable $\Rightarrow$ No superset of $L_1 \cup L_2$ is decidable 2.)...
1
vote
3answers
309 views

Is $L = \{a^jb^ia^{j-i}\mid i,j \ge 0\ , j > i\}$ context-free?

I'm exercising for an upcoming exam and I find this exercise: Say whether or not the language $$L = \{a^jb^ia^{j-i}\mid i,j \ge 0\ , j > i\}$$ is a context-free language. Justify your ...
1
vote
1answer
680 views

CNF: Recursion in CFG

How can I deal with recursive terminals in CFG when converting it to CNF? For example, S -> MN M -> AM | A N -> BN | B A -> a B -> b How can I reduce terminals M and N?
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).
2
votes
1answer
104 views

Is $L$ always context free?

Consider formal language $L$ over finite alphabet $\Sigma$ consisting of all words over $\Sigma$ that have non-trivial period (non empty prefix that is also a suffix). Is $L$ always context free? ...
3
votes
2answers
889 views

PDA for this context-free grammar

I have the following CFG $G$: $$ \begin{align} S &\rightarrow aAbb \mid aaBb \\ A &\rightarrow aAbb \mid \epsilon \\ B &\rightarrow aaBb \mid \epsilon \\ \end{align} $$ I have to create a ...
2
votes
2answers
3k views

Easiest way to write a grammar?

When I see a problem like "Write a grammar for a language $L$ if $L = \{..\}$" for me is a matter of "instinct" the way that one can define productions. For example given the following exercise: ...
0
votes
0answers
139 views

Reduction CVP to CFG problem

I want to show that non-emptiness of context free language is P-complete. So, I am trying to reduce CVP to this problem by generating grammar from circuit. I consider all type of gates in circuit and ...
2
votes
3answers
233 views

Weak Precedence Grammar and Parsing

I am studying parsing, i.e. bottom-up parsing. it is said that there some rules which are used by weak precedence grammar. What does weak precedence grammar mean? What about precedence relation? Any ...
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
886 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
211 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
712 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
179 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
175 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
545 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} ...