# Questions tagged [context-free]

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

1,214 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
208 views

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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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
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 ...
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}$?
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 ...
2k views

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.)...
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 ...
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?
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).
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? ...
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 ...
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: ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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)$ ...
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$ ...
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 ...
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 ...
61 views