# Questions tagged [context-free]

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

1,735 questions
Filter by
Sorted by
Tagged with
48 views

### Possible mistake in a book regarding parsing and lexical analysis

I was just reading a book (Algorithms and Theory of Computation Handbook, Volume 1) and I came across the following passage : "From a practical point of view, for each grammar G = (Σ,V, S, P) ...
1 vote
47 views

### Alternative solution for the Dangling Else Problem

I understand that one of the ways to solve the Dangling Else Problem is by imposing innermost binding. So, we have to transform the following ambiguous grammar: ...
43 views

• 73
669 views

• 213
22 views

### Is complement of this language context-free? [duplicate]

Let $L = \{wcw : w \in \{a, b\}^\ast\} \subseteq \{a, b, c\}^\ast$. From what I know, this language is not a context-free language but how about complement of this language? I know that the class of ...
• 1
36 views

### Context Free Grammar: How to infer FIRST()

We are given the grammar rules $A \to F B E$ $B\to A C$ These rules are only some of the rules of a larger grammar $G$, but we are not given the remaining rules of $G$. We are told that $A$ is ...
• 97
54 views

### A context-sensite grammar for the language of sequences of two different types of parentheses with possible intersections?

Consider the language $L$ over the alphabet (,[,),] such that any word $w \in L$ if formed as a shuffle of two (possible empty) well-formed sequence of parenthesis: one over (,) and another over [,]. ...
• 103
114 views

### Is matching pairs sufficient?

Book PDF: https://vishub.org/officedocs/13770.pdf Pg 253 of book This is a snapshot from Dexter C. Kozen - Automata and Computability, Lecture-35, Undecidable problems about CFLs. My question here is ...
1 vote
71 views

### Finding the Smallest Language Class containing a given language definition

Given two regular languages L1 and L2 over alphabet Σ, we define the operator RQ(L1, L2) = {w | there exists a word v in L2 such that wv is in L1}. The task is to determine the smallest language class ...
• 11
64 views

### Creating a context-sensitive grammar (CSG) for the language L = {anbna2n: n ≥ 1}

Need a grammar that can create this language, I am having issues getting a language to work and was looking for help.
1 vote
54 views

### A proof that $a^n b^m$ for $n\neq m$ is not regular by using the pumping lemma

I am looking at $L=\{a^nb^m |n\neq m \}$. I would like to prove that $L$ is not regular. This can easily done by assuming it is regular and looking at $\overline L$, or by using other theorems. ...
• 465
1 vote
90 views

### Subset Relations Between CFGs and Their Languages

Is it possible for there to exist two context-free grammars where the set of rules of the first is a proper subset of the set of rules of the second, yet the language generated by the second grammar ...
• 15
83 views

### What is the regular language for L = {w | w has even length, and starts and ends with the same symbol}?

I originally thought it was 0(01)*(01)0 U 1(01)(01)1 where: two versions: one that starts and ends with 0, the other that starts and ends with 1 connected by plus, which does not mean union of both ...
• 13
1 vote
36 views

### Efficiently generating valid strings from a deterministic CFG, one symbol at a time, subject to a length limit

Background I'm writing algorithms for generating arbitrary strings from a formal language $L \subseteq \Sigma^*$, one symbol at a time from left to right, while also ensuring that the strings do not ...
• 121
1 vote
37 views

### Parse tree choices for proving the pumping lemma for CFL

I was studying pumping lemma for CFL and in the proof it says that, we choose the shortest parse tree if there are multiple parse trees and we also choose $R$ the repeating variable such that it's the ...
• 71
1 vote
78 views

### A problem maybe related to pattern-matching

Let $\Sigma_{1}=\{a,b\}$ and $\Sigma_{2}=\{t,f\}$. Define the function $f_{w}:\Sigma_{1}^{*}\rightarrow\Sigma_{2}^{*}$ for every $w\in\Sigma_{1}^{*}$; $f_{w}(w')\in\Sigma_{2}^{*}$ is the word obtained ...
• 11
18 views

• 355
707 views

### Is there a one-state PDA that recognizes every context free language?

Here, I read this: For all CFL, there is a one-state PDA that recognizes this language. What is the proof/idea behind this claim? CFL: Context Free Languages PDA: Push Down Automaton
• 165
1 vote
456 views

### Proving that L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not a context free language

I've been working on proving that this language L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not Context Free. "na(x)" stands for "number of ...
1 vote
90 views

### How to construct context-free language $L$ to prove $L′=\{x|xx∈L\}$ is not context-free?

Can someone please explain me how to solve this? In this post here was one user sketching the solution but I still don't understand how to construct a context-free language $L$ in such a way that the ...
• 23
96 views

### How to put the given context-free grammar into Chomsky Normal Form?

I have questions about how to put the grammar below in CNF - Chomsky Normal Form: S ->aAa | bBb | ВВ; A -> C; B -> S | A; C -> S | ε; I did it like this: I eliminated empty productions: ...
65 views

### Is there a linear language $L$ such that $\overline{L} \in \texttt{Type-2} \setminus \texttt{Lin}$?

This question is kind of a follow-up to a question asked a few days ago. Both of the non-linear complements of linear languages found were also not context free. So the question is this: Is there some ...
• 1,372
62 views

### Can Shared Packed Parse Forest have more than 2 families?

I am implementing Earley parser and using algorithm from Elizabeth Scott's paper "SPPF-Style Parsing From Earley Recognisers" (section 4). Author says A family of children of u will consist ...
• 275
1 vote
46 views

### Accept $L=\{ww^r:w\in\Sigma^*\}$ in less that $|w|$ storage

Suppose $L=\{ww^r:w\in\Sigma^*\}$. Already, we know that we can draw a PDA for $L$ such that accept each $w\in L$ with space complexity at least $|w|$. My question is how is it possible to draw a PDA ...
• 1,942
63 views

### How it possible given string belong to given grammar

Consider this context-free grammar: $$G:\\\;\; S\to aSbb|aaSbbb|\lambda$$ Is the string $a^{2020} b^{4020}\in L(G)$? I try to derive such a string but I can't, how it possible?
• 1,942
We know that Linear context-free languages are not closed under complement, so I encountered a challenge in finding an example to show the above theorem. I think the complement of $L={a^nb^n}$ is not ...