The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Questions tagged [context-free]

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

1,157 questions
Filter by
Sorted by
Tagged with
13k views

### What is complement of Context-free languages?

I need to know what class of CFL is closed under i.e. what set is complement of CFL. I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I ...
150 views

1k views

### Recursive-Descent Predictive Parser for $S \rightarrow 0S1\ |\ 01$

I am having difficulty with one of the exercises in the Dragon Book: Exercise 2.4.1(c): Construct recursive-descent parsers, starting with the following grammars: $$S \rightarrow 0S1\ |\ 01$$...
215 views

5k views

### Context-free grammar for $\{ a^n b^m a^{n+m} \}$

I've got a problem with this task. I should declare a context-free grammar for this language: $\qquad \displaystyle L := \{\, a^nb^ma^{n+m} : n,m \in \mathbb{N}\,\}$ My idea is: We need a start ...
8k views

### Removing Left Recursion from Context-Free Grammars - Ordering of nonterminals

I have recently implemented the Paull's algorithm for removing left-recursion from context-free grammars: Assign an ordering $A_1, \dots, A_n$ to the nonterminals of the grammar. for $i := 1$ ...
611 views

### Proof that $\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \}$ is not (co-)recursively enumerable

I would like to use your help with the following problem: $L=\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \}$. Show that $L \notin RE \cup CoRE$. I know that to prove $L\notin RE$, it is enough to find a ...
2k views

### Decide whether a context-free languages can be accepted by a deterministic pushdown automaton

Given a context-free grammar G, there exists a Nondeterministic Pushdown Automaton N that accepts exactly the language G accepts. (and visa versa) There may also exist a Deterministic Pushdown ...
7k views

### Relation between simple and regular grammars

I am reading "An Introduction to Formal Languages and Automata" written by Peter Linz and after reading the first five chapters I face below problem with simple and regular (especially right linear) ...
For the purpose of proving that they are not regular, what closure properties can I use to transform the languages $L_a = \{ a^*cw \mid w \in \{a,b \}^* \land |w|_a = |w|_b \}$ and $L_b = \{ab^{i_1}... 3answers 2k views ### If$L$is context-free and$R$is regular, then$L / R$is context-free? I'm am stuck solving the next exercise: Argue that if$L$is context-free and$R$is regular, then$L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} $(i.e. the right quotient) is context-... 1answer 571 views ### A context free grammar proof There is a problem which I cannot solve. If you give a tip I will be very glad. Prove that following language is not context free:$L= \{ a^nb^m | \gcd(n,m) = 1 \}$. It can be proven using the ... 1answer 355 views ### The operator$A(L)= \{w \mid ww \in L\}$Consider the operator$A(L)= \{w \mid ww \in L\}$. Apparently, the class of context free languages is not closed against$A$. Still, after a lot of thinking, I can't find any CFL for which$A(L)$... 4answers 375 views ### Why does$A(L)= \{ w_1w_2: |w_1|=|w_2|$and$w_1, w_2^R \in L \}$generate a context free language for regular$L$? How can I prove that the language that the operator$A$defines for regular language$L$is a context free language.$A(L)= \{ w_1w_2: |w_1|=|w_2|$and$w_1, w_2^R \in L \}$, where$x^R$is the ... 2answers 339 views ### Is$A=\{ w \in \{a,b,c\}^* \mid \#_a(w)+ 2\#_b(w) = 3\#_c(w)\}$a CFG? I wonder whether the following language is a context free language: $$A = \{w \in \{a,b,c\}^* \mid \#_a(w) + 2\#_b(w) = 3\#c(w)\}$$ where$\#_x(w)$is the number of occurrences of$x$in$w$. I can't ... 1answer 278 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 ... 1answer 980 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 ? ... 4answers 4k 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 ... 2answers 998 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 ... 3answers 184 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$... 5answers 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 ... 2answers 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. ... 2answers 4k views ### How can I prove this language is not context-free? 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-... 1answer 384 views ### Given a string and a CFG, what characters can follow the string (in the sentential forms of the CFG)? 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$...
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 ...