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
1answer
520 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
208 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
181 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
374 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 ...
3
votes
3answers
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
169 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
108 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
752 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
595 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
78 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
206 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
311 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
739 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
106 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
908 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
141 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
257 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
20k 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
230 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
725 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
183 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
186 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
556 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
352 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 ...