A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Questions tagged [context-free]

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

Filter by
Sorted by
Tagged with
1
vote
2answers
46 views

CFG where u has same number of 1s as v [closed]

$$L=\{uv\in\{0,1,2\}^*\mid u\in\{0,1\}^*,v\in\{1,2\}^*, \text{ and }u\text{ has the same number of 1s as }v\}.$$ Here is my attempt solution, but it is not completely correct, any hint is appreciated ...
1
vote
1answer
75 views

Is there a context-free grammar for $L = \{a^{2^n}| n \geq 1\}$? [duplicate]

I was trying to find a cf-grammar for $L = \{a^{2^n}| n \geq 1\}$ but I cannot seem to find one. Is there a cf-grammar or does it not exist because of the quadratic-exponent?
1
vote
1answer
633 views

Decidability of determining whether a context-free grammar generates all strings in 1*

How could I prove that the following language is decidable? $\{\langle G\rangle \mid G\ \text{is a CFG over}\ \{0,1\}\ \text{and}\ 1^* \subseteq L(G)\}$ P.S. It's the problem 4.15 of the third ...
-1
votes
2answers
52 views

Context-free grammars for two languages

How do I write context-free grammars for the following languages? $B_2 = \{0^n1^n \mid n > 0\} \cup \{0^n1^{2n} \mid n > 0\}$ $B_3 = \{a^nb^mc^k \mid k = n+m\}$ Can someone help me? I'm not ...
0
votes
0answers
13 views

Non-context free languages with word degree [duplicate]

I have stumbled across these 2 problems $L_1= \{\alpha \mid w \in \{a,b\}^* | \alpha $ has exactly 2 b's$\} $ ,prove that $L =\{ \alpha^n | \alpha ∈ L_1 ,n \ge 0 \}$ is not context free Given : $...
-2
votes
1answer
39 views

Context free languages [closed]

I have stumbled on this question: Which of the following languages over the alphabet ${a,b,c,d}$ are context-free and which not ? a) $L_{1} = \{wa^{3n+1}b^nw^{R} \mid w\in \{c,d\}^*,\ n>0\}$; b)...
5
votes
2answers
512 views

Why is the start symbol “not allowed” on the right hand side in Chomsky normal form?

I had a question regarding CNF (Chomsky normal form) in formal language theory. I noticed that a lot of authors (including my own professor, and the Wikipedia page for CNF) frown upon or don't allow ...
0
votes
1answer
62 views

Context-free grammar from language

I'm trying to come up with a context-free grammar for the following language: $$L = \{a^mb^nc^{m+n}\mid 0 \le n \le m\}$$ My thinking is that i can rewrite this to $$L = \{a^mb^nc^nc^m\mid 0 \le n \...
2
votes
2answers
108 views

Proving $L'=\{uv : u \in L \; \land v \in L^R \; \land |u|=|v|\}$ is a CFL with closure properties [duplicate]

Given a language $L$ over $\Sigma=\{a,b\}$ let us define $L'=\{uv : u \in L \; \land v \in L^R \; \land |u|=|v|\}$ Prove: if $L$ is regular, then $L'$ is a context free language. I know how to ...
3
votes
1answer
408 views

Solving the emptiness problem for a CFG in Chomsky normal form (linear)

Given a CFG in Chomsky normal form, is there an algorithm that solves the emptiness problem in linear runtime? I thought about using depth search here, but I think it's a little bit above linear ...
5
votes
1answer
410 views

Removing lambda-productions when it's at the start symbol

I had a question regarding removing lambda-productions from context-free grammars. I understand that the basic theorem or process for removing lambda-productions is to find nullable productions and ...
2
votes
1answer
42 views

CFLs are inherently unambiguous?

As reading the textbook of Introduction to the theory of computation_third edition - Michael Sipser, which have the concept that we call a context-free language L inherently unambiguous if there does ...
0
votes
2answers
1k views

Making a CFG for a^i b^j c^k such that i+j = 3k

I have the language $L = \{a^i b^j c^k \mid i+j=3k\}$, however I am struggling to convert it to a CFG. I have made it into a PDA fairly easily, its just now getting this to the CFG which is the issue....
1
vote
2answers
199 views

Union of two non-context-free languages

Let L1 = L2 union L3 find values such that L1 is context free and L2 and L3 are not. So far I have: L1 = $a^nb^n$ L2 = $a^*b^*$ L3 = $a^+b^+$ Is this acceptable?? Since L2 covers everything ...
0
votes
0answers
144 views

When proof by induction on length string is not possible?

I found out an exercise where you have to prove the correctness of the following CFG: Let $L=\{ 0^i 1^j|2i \leq j \leq 3i \}\:$ and $\: G: S\rightarrow 0S11 | 0S111| \epsilon$ claim: Every string $w ...
2
votes
2answers
192 views

Closure of context-free languages under regular quotient [duplicate]

Knowing that $C$ is a context-free language and $R$ is a regular language, how to prove that $C / R = \{w| \exists x \in R: wx \in C\}$ is also a context-free language?
0
votes
0answers
35 views

Prove the language L of all palindromes over {0,1} is in NP

Wouldn't this language be in P, since it is a context free language. And every context free language is a member of P? Or would it be otherwise?
4
votes
2answers
6k views

Why are CFLs not closed under intersection?

I'm struggling with understanding how context free languages can be closed under union but are not closed under intersection. I was wondering if there was a simple proof or example demonstrating that ...
0
votes
0answers
66 views

Where is proof that palindrom language is nondeterministic? [duplicate]

It is well-known that the language over $T$ with at least 2 symbols is nondeterministic. for simplicity, the language $\{ww^R: w\in\{a,b\}\}$ (even-length palindroms of $a$, $b$) is context-free, but ...
0
votes
0answers
77 views

Is $\{ a^i b^j c^k : i + 1000\ < j + 100 < k \}$ context-free?

I have this language: $$ L = \{ a^i b^j c^k : i + 1000\ < j + 100 < k \}, $$ and what I believe is that we can't prove with the Pumping Lemma that it is not context-free, because we would ...
1
vote
1answer
144 views

Construct a grammar over {$a,b$} whose language is {${a^mb^ia^n | i = m+n}$}

I am a little confused on how to approach this problem. I am unsure how to construct both parts of the grammar using a context-free grammar. This is as far as I got, but this will end up producing a'...
2
votes
1answer
86 views

Extended grammar form (backus-naur) and simple grammar forms equivalence

Square braces around a grammar symbol or symbols denote that these constructs are optional. Thus, production A -> X[Y]Z has the same effect as the two productions A -> XYZ and A -> XZ. Curly braces ...
1
vote
1answer
482 views

Proving that a context-free grammar is unambiguous [duplicate]

I have to find an unambiguous context-free grammar that generates the following language. $$L= \{ w \in \{a,b\}^+ : |w|_a = |w|_b\}$$ I think I have found the context-free one, it should be this one. $...
0
votes
0answers
13 views

How do we determine p (pumping length) in pumping lemma for CFL? [duplicate]

This has been confusing me for a while, how do we exactly choose the pumping length when we want to prove whether a language is CFL or not. For example, when we want to prove that {ww, w: {0,1}* } why ...
2
votes
1answer
222 views

Generating all words of length n in a CFG

Given a CFG for a (infinite) language $L$, is there an efficient algorithm that generates all possible words of length $n$ in $L$? Preferably efficient in time, and with low memory usage. I'm only ...
1
vote
1answer
810 views

Is the union of two non-regular context-free languages always non-regular?

I had this question in my HW: Prove of disprove: If $L_1$ and $L_2$ are non-regular context free languages then $L_1 ∪ L_2$ is not regular. My intuition is that it is wrong. I thought about the ...
1
vote
1answer
45 views

Decide whether this language is regular

Decide whether the language $L$, defined by the following grammar is regular or not: $S \rightarrow aab$ $S \rightarrow aacSb$ $S \rightarrow acSab$ $S \rightarrow acSacSb$ Where should I start? I ...
1
vote
2answers
219 views

Is it possible to create a CFG with succesive palindromes?

In one of my homework I am requested to find a Context-free-grammar (CFG) and a push down automaton (PDA) for the following language: $L = \{x_1\#x_2\#...\#x_k | k \geq 2, \text{ each } x_i \in \{a, ...
0
votes
1answer
467 views

Is every decidable language a deterministic context free language?

I'm trying to get a better understanding for the relationship between decidability and a few other things so that I can get a better grasp of the topic. Any info helps! Is every decidable language a ...
1
vote
0answers
110 views

Is star closure of reverse of grammar equivalent to reverse of closure of that grammar

I need to proof if that it's true or not. $ (G^R)^* = (G^*)^R $ If $G$ is a CFG and $ G = \langle V, \Sigma, \delta, S \rangle $ where $ V $ = Set of Variables or Non-Terminal Symbols $ \Sigma $ = ...
1
vote
1answer
60 views

Problem with forming a context-free grammar describing a language

I've been trying for hours to figure out, how to form a CFG describing this language $L$: $$L=\{ w\in\{a,b\}^* \mid w\text{ is of the form }a^nxb^{n+2}\text{, where }x\text{ is a string of length }3\...
0
votes
0answers
39 views

Give context-free grammars that generate formulas in: [duplicate]

Give context-free grammars that generate formulas in propositional calculus, taking into account: variables represented by single lowercase letter Operations are conjunction (∧), disjunction (∨), ...
1
vote
1answer
422 views

Is the set of all Context free languages a Context sensitive Language? ( can we build a LBA that decides whether a given language is CFL or not?)

What i mean is that can we code each CFL ( the same way we code each turing machine in the Universal Turing Machine ) and build a Linear bounded Automata in such a way that for each input ( which is a ...
8
votes
2answers
268 views

Is {a^n (a+b)^n | n>0} a Deterministic CFL?

$L = \{ a^n (a+b)^n | n>0\}$ A book I'm reading says it is, but considering we can't know where the second part gonna start, and it might start with a as well, then how can we accept this using ...
0
votes
1answer
142 views

Pushdown Automaton for $L = \{ w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2 \} $

So i know that $L =$ { $ {w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2} $ } is a CFL, but i cannot make a PDA for it because it doesn't make any sense to me why this is CFL i even know the grammar for it ...
0
votes
1answer
229 views

Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language L = {aibjck |i ≠j ≠ k ≠ i } is not context free

Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language $L = \{a^ib^jc^k \mid i ≠j ≠ k ≠ i \}$ is not context free. From my understanding, we want to prove that all 3 ...
2
votes
1answer
200 views

Should we eliminate left recursion before using NPDA to simulate CFG?

I read the book "Introduction to the Theory of. Computation, Third Edition by Michael Sipser". It says: If a language is context free, then some pushdown automaton recognizes it. Let A be a ...
1
vote
1answer
215 views

Prove that the language $L_1 = \{a^ib^{2i}c^j \;|\; i,j ≥ 0\}$ is context-free

Prove that the language $L_1 = \{a^ib^{2i}c^j \;|\; i,j ≥ 0\}$ is context-free. I have a grammar like this but there are some strings that are not be able to be generated $$\begin{align} S &\to ...
0
votes
0answers
107 views

Are there any context-free languages that are not regular but can be generated using a right-linear or left-linear grammar?

I understand that every regular language can be generated using either a right-linear or left-linear grammar, however, does that go the other direction? In other words, do there exist any context-free ...
6
votes
2answers
89 views

Can the regular image of a context-free language be undecidable?

I just need to know the truth or falsity of a simple statement. Let $L_1$ be a context-free language over an alphabet which contains some number of characters $\Sigma$, as well as a single, special ...
2
votes
0answers
83 views

Looking for a subclass of deterministic context-free languages, other than the subclass of regular languages

Let $X=\{x_1,\ldots,x_n\}$ be a finite set of alphabet and $X^\ast$ denote the set of all words (including empty word) over $X$. Clearly, $X^\ast$ is a regular language. Is there a subclass, say $C$, ...
2
votes
1answer
221 views

Is set of all regular languages on a specific alphabet a regular language?

so i know that the set of all strings over any finite alphabet is countable, but this question is different so if our language is set of all regular languages(or set of all regular expressions) on a ...
0
votes
1answer
56 views

How to define whitespace for certain rules but else ignore it

I am trying to make a programming language for the first time and wonder how it handles whitespace. I can see CFG by default seem to just ignore whitespaces, but what if I want it to use it sometimes? ...
1
vote
2answers
111 views

CFG - Left factoring in recursive nested productions

I'm attempting to convert a CFG into an LL(1) grammar for predictive parsing in a compiler. I've been able to left factor and eliminate left recursion and ambiguity for every case in the grammar, with ...
2
votes
1answer
141 views

Proving ambiguity of this Context Free Grammar

I ran into this exercise problem from Introduction To The Theory Of Computation by Sipser. Given a context free grammar: $ S \rightarrow SS \ | \ T \\ T \rightarrow aTb \ | \ ab $ I have to show ...
4
votes
1answer
392 views

Basic doubt in converting PDA to DPDA

This is the PDA to accept strings with equal number of $a$'s and $b$'s. The $\epsilon$ transition in the first state is causing nondeterminism. When we have input a with Z at the bottom of the stack, ...
1
vote
0answers
59 views

Constructing Context Free Grammar with 3 terminal symbols, with two dependent pairs

I am new to Context Free Grammars and am having trouble wrapping my head around how to approach writing a CFG for the following language: ...
0
votes
1answer
36 views

Explain why a language can be generated by a context free grammar [duplicate]

I have a problem where I am asked to explain why the language that has words made of $a$ and $b$ such that the number of $a$'s is equal to the number of $b$'s, can be generated by a context free ...
1
vote
2answers
71 views

Can a DPDA decide if two letters appear the same number of times mod 5?

$ L = \{ w ∈\{0,1\}^* \mid |w|_0 = |w|_1 \mod 5 \}$ So i tried figuring out why this is CFL and whether its DCFL or not but i couldn't come up with any PDA! I'm studying for my exam and this ...
1
vote
0answers
43 views

Is DCFL closed under union with RL? [duplicate]

So i know that DCFL is not closed under union, but what about union with RL? Because what if both of the languages can start with the same string?then when we are building the DPDA for the union and ...