# Questions tagged [context-free]

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

1,191 questions
Filter by
Sorted by
Tagged with
32 views

### How to prove that a language is not context-free using pumping lemma

I'm trying to prove that that language isn't a context free: $L = \{ w11w \mid w\in \Sigma^* = \{0,1\}\}$ I succeed to prove that $L = ww$ isn't context free, but not the language above. What ...
40 views

### Find PDA for CFL = {x#y | |x| = |y| and x ≠ y} [duplicate]

I am studying push down automata. When I read a solution for showing $L = \{x\#y \mid x \neq y, x,y \in \{0,1\}^*\}$ is a CFL, I could understand $L = L_1 \cup L_2$, $L_1 = \{x\#y\mid|x| \neq |y|\}$, ...
57 views

### Creating a CFG from a specific CFL

I am pretty desperate finding the correct context free grammar for the following language: $$L=\{a^lb^mc^n \mid l,m,n \in \mathbb{N}_0, \, l\geq 2n+m\}$$ I would really appreciate if anyone could ...
23 views

I was learned NPDA is specified by a tuple $P = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$, $Q$ is a finite set of states $\Sigma$ is a finite set of input symbols (input alphabet) $\Gamma$ is a finite ...
48 views

### Proving that the set of grammars generating L or L complement is undecidable

Let $X$ be a regular language, I need to prove that either $\{G \mid L(G) = X\}$ or $\{G \mid L(G) = \overline{X} \}$ is undecidable using the following hint: Use reduction to absurdity supposing that ...
37 views

### Undecidability of checking whether all words can be generated from a context-free grammar?

I know it's undecidable, but how to prove it? Let me explain the problem clearer. The problem is not to check whether some given word can be generated, but whether ALL words are possible to generate ...
57 views

### Is there an algorithm to overapproximate a context free grammar by a regular expression?

I understand that a context-free grammar is strictly powerful than a regular expression in that a context free grammar can represent any regular language, but not all context free languages can be ...
422 views

### Convert this language to Context Free Grammar

I'm having trouble understanding how to convert this language to context free grammar. $\{a^ib^jc^k\mid i > k, 0\le j \lt3, k \ge 0\}$ Part im getting stuck on is how to deal with a and c, ...
568 views

### CFG for L {a^nb^m | n <= m+3}

I need a Context Free Grammar for this language. I could come up with this solution: S -> AB A -> aA | ε B -> bbbB | ε But, this grammar is clearly ...
197 views

$L =\{a^nw \mid w \in \{b,c\}^*$, $n=$ #$_b$ + #_c$$\} \bullet #_b denotes the number of b's in w \bullet #_c denotes the number of c's in w I have some trouble designing a CFG ... 1answer 169 views ### Constructing PDA to accept language { 0^i 1^j 2^k | i = 2j or i = k, where i,j,k >= 1 } L = \{ 0^i 1^j 2^k \mid i = 2j \text{ or } i = k, \text{ where } i,j,k \geq 1 \} I have trouble about this PDA. Anybody can help me about draw this PDA? 0answers 35 views ### Is there any grammar parseable by LALR(1) but not LR(1)? https://en.wikipedia.org/wiki/LALR_parser - as far as I understand, LALR(1) is a simplified version of LR(1), aiming to achieve a greater parsing performance at the expense of reduced power. So, IIUC, ... 1answer 50 views ### What are the sufficient conditions for a grammar to be unambiguous? There is no algorithm that, given an arbitrary grammar, decides if it's ambiguous or not. However, Are there any sufficient conditions that make it easier to tell that a grammar is unambiguous? For ... 2answers 61 views ### Operator name in LL(1) computation I'm working from a definition of the LL(1) property of context-free languages in order to build a LL(1)-computer, i.e., a program capable of determining whether a given context-free language is in LL(... 0answers 247 views ### a^nb^nc^nd^n using 2-stack PDA I need to construct a PDA using 2 stacks for accepting the language L = \{a^nb^nc^nd^n | n \geq 0\}. Pushing a's to first stack and b's to second and poping them for corresponding c's and ... 2answers 52 views ### Why can we (apparently) implement CFG parsers only using (N)DFAs? I am working on a project in which I need to parse files written in different DSLs. One important feature of these languages is that most of them allow blocks to be nested. For parsing those files I ... 1answer 243 views ### Binary strings such that the sum of 0's is not equal to twice the sum of 1's Construct a context-free language for L=\{w\in \{0,1\}^* \mid n_0(w)\not= 2n_1(w)\}. Here n_b(w) is the number of b's in w. I can construct a CFL in the case n_0(w)=2n_1(w), but I have no ... 1answer 99 views ### Finding an unambiguous grammar of a language provided by a CFG I'm working through 'Intro to Automata Theory, Language and Computation' 2nd edition by Hopcroft, Motwani & Ullman. In section 5.4, exercise 5.4.3 I am tasked with finding an unambiguous grammar ... 2answers 114 views ### How do I model line comments in a CFG? Assume we want to define a context free grammar of say a programming language, where on each line everything after the character # until the end of line is considered a comment and should be ignored. ... 0answers 87 views ### Accounting for spaces in grammars Sometimes in a context free language we'd like to require spaces between productions, and sometimes not. For example take the following part from a grammar describing grammars: ... 1answer 51 views ### Can the complement of a context-free language be regular? I know that the context-free language is not closed under the complement , and the result could be context-free language or non-context free language but my question is : is it possible of the ... 1answer 34 views ### Equivalent unambiguous grammar Given the grammar: S \to AS\mid \varepsilon A \to A1\mid 0A1 \mid \varepsilon Generate a new unambiguous grammar that generates the same language as the grammar above. I have no idea how to ... 2answers 38 views ### Proving that a specific grammar is ambiguous How can I prove that the following grammar is ambiguous:$$ A \to AA\mid B \\ B \to aBb\mid ab $$I tried finding a string that can be derived in two different ways, but to no avail. 1answer 51 views ### Crafting a Context Free Grammar I'm trying to figure out the intuition on creating a CFG in my head. I understand the idea of Grammar rules akin to "onions" with various layers throughout. For example, I was working on a problem ... 3answers 55 views ### When are two CFG's different? If two CFG's differ only in what names they use for their non-terminals, are they different? For example, are these CFG's different:$$\begin{align*} S &\to A \\ A &\to a \end{align*}$$and ... 1answer 86 views ### The language \{ww \mid w \in \{0,1\}^{*} \} is not a CFL We have proved that the language L = \{\omega\omega \mid \omega \in \{0,1\}^{*} \} is not a CFL, and we did so by using pumping lemma. And the proof is clear to me. But I thought of the following ... 1answer 326 views ### Language whose intersection with a CFL is always a CFL Prove or disprove: If the language L is such that for every context-free language L_0, the language L \cap L_0 is context-free, then L is regular. I haven't managed to prove this, but I'm ... 1answer 58 views ### Finding a mapping reduction from A_{TM} to \overline{CF_{TM}} I am trying to find a mapping reduction from A_{TM} to \overline{CF_{TM}}, but I can't seem to find one. Definitions:$$\begin{align*} CF_{TM} &= \left\{ \langle M \rangle \mid \text{M$is a ... 1answer 74 views ### Context Sensitive Grammar for the language$\{a^n b^n c^{2+k}\mid n \ge 1, 0 \le k\le 1\}$[closed] I'm studying for my final exam and come up with this exercise with no idea how to find the production rule of this grammar. I need help. Thanks all of you! :) 1answer 35 views ### Is substitution done to all occurrences? In a CFG, we might have :$A \rightarrow AA$and$A \rightarrow a$where$a$is a terminal and$A$is a variable. Then if we apply the first rule, and then the second , do we get$aa$or either$aA$... 3answers 91 views ### Are$CF_{TM}$,$\space \overline{CF_{TM}}$Turing-recognizable? I have searched the site well through, and also using Google and notes and couldn't find an answer to a question I am wondering about. Given: $$CF_{TM} =\{ \langle M \rangle \mid \text{M is a TM ... 0answers 31 views ### Generating context-free grammar from language [duplicate] I need to give a context-free grammar for each of the examples: L_1=\{a^hb^ka^mb^n : h+k=m+n\} L_2=\{a^ib^ja^k : (i=j \,\,\,\, and \,\,\,\, k≥0) \,\,\,\, or \,\,\,\, (i\ge0 \,\,\,\, and \,\,\... 0answers 32 views ### How to make the length even for the words whose number of 0s is double its number of 1s? [duplicate] How do I make a context-free grammar (CFG) for the following language?$$L = \{w \in \{0, 1\}^* : \#_0(w) = 2\#_1(w)\text{ and } |w|\text{ is even}\}.$$I have$$S \to S1S0S0S \mid S0S1S0S \mid ... 1answer 242 views ### For any two regular languages A, B, show that {xy|x ∈ A, y ∈ B, |x| = |y|} is context-free Basically I'm wondering if the concatenation of two equal length string is context free. I've seen multiple proofs of this online using PDAs but we aren't covering them in my automata course and my ... 1answer 150 views ### Is a kind of reverse Kleene star of a context-free language context-free? Recently I had a question on one of my assignments asking to prove or disprove the following: Let$L$be a language. If$L^*$is context-free then$L$is context-free. Now obviously this is false ... 1answer 97 views ### Proving that L(G) is the language defined by the CFG G I have a context-free grammar defined by the production S: S → aSbS ∣ bSaS ∣ ε I need to prove that the CFG "G" can be defined as a language L(G) where L(G) = {w ∈ {a, b}∗ ∶ na(w) = nb(w)}. ... 0answers 71 views ### How to generate random strings from Context-Free Grammar in GNF I need to generate random strings given a grammar in Greibach Normal Form. The naive approach would be to generate a random integer n and perform ... 1answer 48 views ### Context free grammar for L={ ((ab)^n)^m } I want to write a cfg for the following language:$ L = {((ab)^n)^m }m,n >= 0$this language produces (abababababab) where:$n=2, m=3 \\ or \\ n=3, m=2$I have no idea what to do with it! 2answers 736 views ### Language involving irrational number is not a CFL I am working through a hard exercise in a textbook, and I just can't figure out how to proceed. Here is the problem. Suppose we have the language$L = \{a^ib^j: i \leq j \gamma, i\geq 0, j\geq 1\}$... 0answers 70 views ### Proving the Complement of a DCFL is DCFL [duplicate] If I Have a DCFL$L$( a CFL which can be recognised by a DPDA ), How do I prove that$\overline{L}$is also a DCFL I checked my textbook for a proof but I wasn't able to understand the language. Can ... 0answers 38 views ### construct regular expression for a language [duplicate] I want a regular expression for the following language. (a+b+c)*, but does not contain substring "abab". That means it can be any combination of (a, b, c) except "abab". I tryed to construct it ... 2answers 82 views ### What is the language L, generated by the grammar G? Given the grammar$G = (Ν, Σ, Π, S)$, where$Ν = \{S\}$,$Σ = \{0, 1\}$,$Π = \{S → ε, S → 0, S → 1, S → 0S0, S → 1S1\}$, and$S$is$S$. What is the language generated by the grammar? 1answer 99 views ### Find a CFG for$\{a^ib^jc^k \mid i,j,k\ge0 , \text{if } j=1 \text{ then } i=k\}\$

I've tried but I can't figure out any solution. Is there any hint for me to solve the question?
45 views

### Is this language is Context-free language or not?

Is anybody can help me please to determine is this language is Context-free language or not? L={wvw | w,v∈{a,b,c}+} for example: part of the language: acbac, abcab, bbcbb not part of the language:...
118 views

### How to find First in a left recursive grammar?

One of the basic requirements for a grammar to be LL(1) is : For every pai r of productions A -> X | Y, First(X) and First(Y) should be disjointed. If a grammar is left-recursive, then the set of ...
52 views

### Create a grammar that generate the language a^n . b^m . c^q . d^p such that n + p = q + m

I'm stuck on this question. I'm struggling on how to keep track of the number of a and d I have generated. The professor hasn't given the correction. I have seen similar questions but the condition ...
44 views

### Is λ allowed in Deterministic CFG?

I have a non-deterministic CFG that says S-> aS | aB | bB | λ; B-> bB | λ And I'm asked to create a deterministic CFG from that. I understand why the given CFG is non-deterministic because it ...
47 views

### Whether it's necessary for a grammar to be ambiguous when it is both left recursive and right recursive

I read somewhere that if a grammar is left recursive as well as right recursive, then it is not necessarily ambiguous. I couldn't make up my mind on this statement. How can a grammar which is both ...