# 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
130 views

### Stuck on Converting to Chomsky Normal Form,

I am supposed to be changing this to Chomsky Normal Form and then to Greibach form, but I am still having a few difficulties changing it to the first form. Here is the language: S → AA|SBBa|b A → ...
1 vote
556 views

### CFG for the language {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}

The question is the following: Construct CFG for the L = {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}. I am able to construct CFG for the set of all palindromes as below: S --> aSa | ...
1 vote
598 views

### Need help understanding what co-recursively enumerable means

Lets say I have a set: $L = \{\langle G \rangle | L(G) = \Sigma^{\star}\}$ and the question asks if it is co-RE. I know that if something is co-RE, it halts on every input not in L but may or may not ...
105 views

### CFG for the given language $L = \{~ a^\ell a^n b^m c^m d^n e^\ell ~|~ \ell,n,m \geq 0 \}$

I am writing this CFG to solve the problem: $S \to ASBSC$ $A \to aAe ~|~ ε$ $B \to aBd ~|~ ε$ $C \to bcC ~|~ ε$ Is this correct or not?
93 views

### Intersection of Infinite Regular Language with CFL

Intersection of any finite regular language with anything( CFL or not CFL) will be finite but what about intersection of infinite regular language with CFL or not CFL. Does the resultant will be ...
36 views

### L = {xy : x, y ∈ {a, b} ∗ , |x| = |y| and x ̸= y^R} where y^R is the reverse of y

How can I convert this context free langauge to conext free grammar? Please help I can not solve this problem for days. L = {xy : x, y ∈ {a, b} ∗ , |x| = |y| and x ̸= y^R} where y^R is the reverse of ...
651 views

### Is the language $L = \{0^i 1^j | i \ne 2j\}$ context free?

I have been trying to find a a CFG for this language generated. I came to the conclusion that I need three parts When $i \le j$ When $j < 2j < i$ When $j < i < 2j$ I was able to come up ...
1 vote
364 views

### Does there exist an context free language L such that L∩L^R is not context free?

By the closure property of context-free languages, if $L$ is context-free, then $L^R$ (the reverse of $L$) is also context-free, but $L\cap L^R$ might be non-context-free. I tried to come up with an ...
33 views

### How do I convert this context free language to context free grammar L1 = {0^i 1^j : i ̸= j, j ̸= 2i}

How do I convert this cfl to cfg L1 = {0^i 1^j : i ̸= j, j ̸= 2i}
49 views

### Derivation trees to show a given grammar is ambiguous

Given the grammar with productions: \begin{align} S \rightarrow aSb \mid SS \mid \lambda\\ \end{align} I would like to show that it is ambiguous. As I understand it, if you can show that some string ...
57 views

### Can we give an example Context-Free Language that a DPDA can not recognize

Can we give an example Context-Free Language that a DPDA can not recognize. If we DPDA can not recognize can you explain why?
29 views

### Proof that $\{0^m 1^n : 0\le m\le n^2\}$ is not a CFL

I am trying to prove by the pumping lemma that $L=\{0^m1^n:0\le m\le n^2\}$ is not a CFL. Here is what I have so far. Suppose for contradiction that it is a CFL and let $N$ be the pumping length. ...
57 views

### Is L={0^n 1^n ∣n≥0} context free language?

I looked through many sources which give this as an example for cfl. It also makes sense according to this: But it fails the pumping lemma test. Let's take n=5. According to the Pumping Lemma, we can ...
79 views

### What could be possible NFA for the RegEx "a?"

I am trying to use the Thompson's method to draw an NFA for a RegEx given by: $(a+b|c?)c$ I am wondering if I should deconstruct the RegEx as - Concatenation of $a+$, $(b|c?)$ together with $c$ OR ...
238 views

### What to do following a reduce in LR(1) parsing?

I am using this standard question from Dragonbook as an example, (the first problem) . I have trouble with what happens in State 4 on LR(1) parsing. Once it is reduced by the rule C->d, now what ...
26 views

### Which one is an LL(2) but not an LL(1)

I'm pretty sure b and d are ll2 and not one but not 100% sure. (a) S → aaScc | aaBbc | aaBbb | aBb | ac | Ʌ B → aBb | Ʌ (b) S → aaScc | aaBbc | aBb | ac | Ʌ B → aBb | Ʌ (c) S → aaScc | aaBbc | B | ac |...
1 vote
771 views

### Understanding this PDA for non-palindromes over {0,1}

I found this PDA online that accepts all non-palindromes over {0,1}. However, I can't seem to understand how it would accept, say "01011", and not accept "101101". Can someone help ...
46 views

### Turing machine for a^n b^m c^n d^m

The state diagram for the initial part of this turing machine given as: Here, we are basically traversing through the input tape, changing occurence of 'a' to X1, and 'c' to X2. After that we go back ...
735 views

### How to determine valid handle for given bottom up parser?

I came across following question: Consider the grammar: $E → E + n\text{ | }E × n\text{ | }n$ For a sentence n + n × n, the handles in the right-sentential form of the reduction are (...
37 views

### Question about $L$ = { $ww$ | $w$ ∊ $ca^*c$}

I found a grammar for this language. $S->caZac |cccc$. $Z->aZa | cc$ But if I try to use pumping lemma for context-free languages on $L$ with the word: $ca^ncca^nc$ I obtain it's not context-...
31 views

### Language of words concatenated with themselves

Let $L$ be a regular language. Is the language $L_2 = \{ ww | w \in L \}$ context-free? Does it have a name?
79 views

### Convert CFG to CNF

I have been struggling with this conversion problem. Would very much appreciate some verification on this. Given: S' -> S $($ is a terminal) S -> a A B | b B A | ε A -> a | S B -> b ...
151 views

### Is $\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j ;\ j \text{ is even, then } k =i+j\}$ context-free?

$L=\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j ;\ j \text{ is even, then } k =i+j\}$ I tried writing $L$ as the union of the language created with $j$ odd and the one with $j$ even. When $j$ is ...
39 views

### How can I transfer the following language into an context-free grammar?

My problem of understanding is how to create a new a before the b's if you create new c's. Hopefully someone can help me out.
9k 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$ to $n$ ...
33 views

### An elementary question about grammar

Recently, I am studying grammar in automata. And, I have few information about this subject. I have a grammar with rules $\{S\to ASA, A\to aA, A\to \epsilon\}$. Is it true if I say that $S\to aASA$ ...
35 views

### Write a CFG for a language of the form L_1 ={a^ib^jc^kd^m|i,j,k>=0, i +j +k> m}

I'm currently having trouble coming with context free grammar to describe this language. My current intuition is to generate an arbitrary amount of a,b,c's on my string and then whenever the character ...
46 views

### Generating parse trees when only a recognizer is given

I am trying to understand "On the complexity of general context-free language parsing and recognition" by Walter L. Ruzzo. One of the results from the paper is about generating a parse tree ...
55 views

### Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s

Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s. Is P' context-free? I know that for the language of ...
1 vote
199 views

### SLR(1) Table construction, FIRST and FOLLOWS

when constructing the SLR(1) table for some grammar I need to compute the FOLLOW set for all terminals in order to decide where and when to reduce. Do I compute theme for the augmented grammar or ...
1 vote
30 views

### How need help to specify a grammar for arithmetic expressions

I am trying to come up with a grammar for arithmetic expressions with the following order of operations: Parentheses Factorials Exponents Functions / unary plus and minus Juxtaposition (implied ...
167 views

### How to demonstrate unambiguous CFG and CNF?

I have to show that if G is an unambiguous CFG, the transformed grammar G' in CNF is also unambiguous. But couldn't come up with something concrete. I could only visualize the case where the grammar G ...
104 views

### Pumping Lemma for $\mathcal{L} = \{ \omega \omega^R a^{|\omega|} : \omega \in \{a,b\}^* \}$

I have to show that this language is not context free $\mathcal{L} = \{ \omega \omega^R a^{|\omega|} : \omega \in \{a,b\}^* \}$, where the $R$ corresponds to the reverse. For this I will use the ...
79 views

### Is $L = \{w w^r w | w \in a(b+c)^*a \}$ a context-free language?

Can't understand how to apply pumping lemma to see if a language is context-free or not. I tried to verify the context-free's pumping lemma, and the language seems to be not context-free but I can't ...
1 vote
139 views

### Dangling else determinism

The natural grammar for dangling "else" is ambiguous. But there exists an unambiguous version of the grammar that links the "else" to last uncompleted "if" statement. Is this version also ...
1 vote
205 views

### Are there any algorithms that decide if a PDA (pushdown automaton) accepts a sentence?

Most computation theory textbooks just mention the equivalence of PDAs and Context Free Grammars. I'm able to construct a PDA from a given CFG, but find it very difficult to write an algo to check if ...
1 vote
84 views

78 views

### Example 7.1 correctness in Introduction to Automata Theory, Languages, and Computation

The example says that C is unreachable, but there is the production S-> aBC so C is clearly reachable. This is an error right? or am I missing something.
1 vote
72 views

### Is $L=\{1^n2^n3^m : n\neq m\}$ context free?

Is the language $L=\{1^n2^n3^m : n\neq m\}$ context free? I checked and it satisfies the pumping lemma (Right?). Does it also satisfy Ogden's lemma, or any other test for being non-context free?
37 views

### Find Grammar for L(G) ={a^i b^j c^k | k = i*j ;i, j ≥ 1}

Find a Grammar G, so that L(G) = {a^i b^j c^k | k = i*j ;i, j ≥ 1} Hello, I have difficulties solving this. I had a similar exercise, where the k was i+j, which was easier, because the solution was to ...
1 vote
168 views

### How to prove L := { a^n b^n c^m | n,m >= 0 & n != m } is not context-free?

I have following language $L:= \{a^n b^n c^m \mid n \neq m; n,m \ge 0 \}$ and would like to use proof by contradiction by applying Pumping Lemma for CFLs to show that $L$ is not a CFL. In any case, i ...
1 vote
50 views

### Does this really define a 0L-system?

Looking through old exams I found a problem stated as the following: Define a 0L-system as a 3-tuple $S = (\Sigma, w, h)$ where $\Sigma$ is an alphabet, $h:\Sigma^* \to \Sigma^*$ is a homomorphism ...
5k views

### Removing epsilon transition from context-free grammar

I have the following context-free grammar from which I have to remove epsilon transitions: $S \to 0A0|0$ $A \to BC|2| CCC$ $B \to 1C | 3D | \epsilon$ $C \to AA3 | \epsilon$ $D \to AAB | 2$ By ...
112 views

### prove or give counterexample about regular language

Let $\Sigma = \{a,b\}$, $L_1,L_2\subseteq \Sigma^*$ $L_1 ◃ L_2 = \{w∈ \Sigma^* | \exists v\in L_1, vw \in L_2\}$ For any context-free language $L$, regular language $R$, whether $L \triangleleft R$ ...
25 views

### Confused about decomposition in Context Free Pumping lemma

Okay so here's my current solution for the question that asks whether the language is context free: $$L = { a^nb^{3n}c^n | \, n \geq 0 }$$ Assume by contradiction that L is context-free. Let p be ...
6k views

### Is Python a context-free language?

From Wikipedia: Off-side_rule#Implementation, there is a statement: ...This requires that the lexer hold state, namely the current indentation level, and thus can detect changes in indentation ...
1 vote
So I have a language: $$L = \{a^{n^2} \mid n > 0\}$$ I need to prove that this language isn't context-free using the pumping lemma. I have a vague thought process as to how to do the proof but I'...