# Questions tagged [context-free]

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

1,681 questions
Filter by
Sorted by
Tagged with
580 views

### Is this language Context-Free?

Is the language $$L = \{a,b\}^* \setminus \{(a^nb^n)^n\mid n \geq1 \}$$ context-free? I believe that the answer is that it is not a CFL, but I can't prove it by Ogden's lemma or Pumping lemma.
1k views

### Eliminating useless productions resulting from PDA to CFG converison

In my class we used a Pushdown Automata to Context Free Grammar conversion algorithm that produces a lot extraneous states. For example, for two transitions, I am getting the following productions ...
31k views

409 views

### Closure against the operator $A(L)=\{ww^Rw \mid w \in L \wedge |w| \lt 2007\}$

I would like your help with the following question: Let $L$ be a language, and operator $A(L)=\{\,ww^Rw \mid w \in L\ \wedge\ |w| \lt 2007\,\}$ where $x^R$ is the reversed string of $x$. Which of ...
2k views

### Chomsky normal form and regular languages

I'd love your help with the following question: Let $G$ be context free grammar in the Chomksy normal form with $k$ variables. Is the language $B = \{ w \in L(G) : |w| >2^k \}$ regular ? ...
8k views

### Prime number CFG and Pumping Lemma

So I have a problem that I'm looking over for an exam that is coming up in my Theory of Computation class. I've had a lot of problems with the pumping lemma, so I was wondering if I might be able to ...
1k views

### Are the Before and After sets for context-free grammars always context-free?

Let $G$ be a context-free grammar. A string of terminals and nonterminals of $G$ is said to be a sentential form of $G$ if you can obtain it by applying productions of $G$ zero or more times to the ...
200 views

### Language of the graph of an affine function

Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let : be a symbol distinct from any digit. Let $a$ and $b$ ...
1k views

### Language of the values of an affine function

Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let $a$ and $b$ be integers, with $a > 0$. Consider the language of the decimal expansions ...
2k views

### Decidablity of Languages of Grammars and Automata

Note this is a question related to study in a CS course at a university, it is NOT homework and can be found here under Fall 2011 exam2. Here are the two questions I'm looking at from a past exam. ...
I have the following language $\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$ I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a context-...
Let $\Sigma$ be the set of terminal and $N$ the set of non-terminal symbols of some context-free grammar $G$. Say I have a string $a \in (\Sigma \cup N)^+$ such that $x a y \in \mathcal{S}(G)$ where $... 14 votes 2 answers 13k views ### Are all context-free and regular languages efficiently decidable? I came across this figure which shows that context-free and regular languages are (proper) subsets of efficient problems (supposedly$\mathrm{P}$). I perfectly understand that efficient problems are a ... 53 votes 1 answer 24k views ### Show that { xy ∣ |x| = |y|, x ≠ y } is context-free I remember coming across the following question about a language that supposedly is context-free, but I was unable to find a proof of the fact. Have I perhaps misremembered the question? Anyway, here'... 98 votes 5 answers 103k views ### How to prove that a language is not context-free? We learned about the class of context-free languages$\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free.... 12 votes 1 answer 5k views ### Is an inﬁnite union of context-free languages always context-free? Let$L_1$,$L_2$,$L_3$,$\dots$be an inﬁnite sequence of context-free languages, each of which is deﬁned over a common alphabet$Σ$. Let$L$be the inﬁnite union of$L_1$,$L_2$,$L_3$,$\dots $; i.... 7 votes 1 answer 690 views ### How to convert a non-embedding context free grammar to regular grammar? A context-free grammar is said to be self-embedding if and only if contains a derivation of the form$\xi\stackrel*\Rightarrow u\xi v$, where$\xi$is a non-terminal and$u$,$v$are some non-empty ... 6 votes 3 answers 3k views ### Closure of Deterministic context-free languages under prefix For a formal language$L \subseteq \Sigma^{*}$I define the set Pref(L) to be:$\text{pref}(L) = \{\alpha \in \Sigma^{*} : \exists \beta \in \Sigma^{*} \text{ such that } \alpha \beta \in L\}$ie. ... 13 votes 1 answer 7k views ### Is there a context free, non-regular language$L$, for which$L^*$is regular? I know that there are non-regular languages, so that$L^*$is regular, but all examples I can find are context-sensitive but not context free. In case there are none how do you prove it? 7 votes 1 answer 801 views ### Converting a context free grammar to a PDA -- is my solution correct? I'm reviewing for my midterm and wanted to post this to see if anyone can spot any errors. Im supposed to make a PDA that recognizes this CFG:$\qquad\begin{align} S &\to R1R1R1 \\ R &\to ... 