# Questions tagged [context-free]

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

1,197 questions
Filter by
Sorted by
Tagged with
112 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?
104 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?
47 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:...
158 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 ...
45 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 ...
49 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 ...
22 views

### (Non) Context Free Language…? [duplicate]

I hope you could help me as you have done before (thanks again) In a previous exam I saw this question; it is asked to identify if the language is Regular, CFL or Non CFL. In my opinion this ...
152 views

### The rightmost derivation is possible with the same rule of leftmost derivation

Can someone please help me in understanding the statement. What does it exactly mean? What I think it means is that: the derivation produces by the leftmost derivation is also possible with rightmost ...
55 views

### Grammar for context free language

I want to give a grammar for the following language: $$L = \{x^r \# y |x, y \in \{a, b, c\}^*\\ \text{ and }x\text{ is a contiguous sub-string of }y\}$$ where $x ^ r$ denotes the backward written ...
49 views

### Is this language L context-free?

The language $$L = \{x^r \# y | x, y \in \{a, b, c\}^*\\ \text{ and }x\text{ is a contiguous sub-string of }y\}$$ where $x ^ r$ denotes the backward written word x, is context-free. Can someone ...
46 views

### Prove by Pumping Lemma that Language $L=\{a^ib^kc^k : i\geq k\geq 1\}$ isn't Context-Free

I'm new to this forum. I have some difficulties on using Pumping Lemma to prove non-CF language. Let $L=\{a^ib^kc^k : i\geq k\geq 1\}$ and the followings are my attempt. Proof. Suppose by ...
60 views

### Does a Context-free language have a grammar that has either 3 or 0 nonterminals on the right hand side?

Is the following true or false? Why? Let L be a context-free language with $\epsilon\notin$ L. Then there is $\epsilon$-free grammar $G=(V,\Sigma, P,S )$ with $L (G) = L$, so all production rules are ...
115 views

### Is this proof for showing that $EQ_{CFG}$ is co-Turing-recognizable incorrect?

I have been searching for proofs that show that $EQ_{CFG}$ is co-Turing-recognizable. When searching for proofs I can only find proofs on the following form: Construct a TM $M$ which recognizes the ...
43 views

### Can the pumping lemma for context free languages be extended to any subword?

It is known that in the case of a Regular Language $L$ , the pumping lemma can be extended to apply to any sufficiently long subword of the language, ie, if $uwv \in L$ and $|w| \ge p$ then we can ...
42 views

### Constructing CFG

How to generate CFG for this language? $L = \{ w \mid w \in \{ (, [, ], ) \}^* \text{ s.t. }$ In any prefix of $w$, no. of ( is more than no. of ), and no. of [ is more than no. of ]. $\}$ Thus,...
53 views

46 views

### Decidability of $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$are CFGs and$L(G) ⊆ L(H)$}\}$

How can I prove that $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$are CFGs and$L(G) ⊆ L(H)$}\}$ is decidable ? I know that $EQ_{CFG} = \{⟨G, H⟩ \mid \text{$G,H$are CFGs and$L(G) = L(H)$}\}$ is not.
35 views

### is $0^x1^y$ context-free?

given that L is regular, does the following make a context-free language?: i) $\{0^x1^y \mid 0^{x+y} \in L\}$ ii) $\{0^x1^y \mid 0^{x-y} \in L\}$ since L is regular, i presumed that i) can be put ...
38 views

### Is the language $L$ of coded CFG's Turing decidable?

Consider the following language $L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$} Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that ...
50 views

### What's the right way to think about a CFG symbol with an infinite null derivation?

I'm curious about the right way to characterize symbol $A$ in a CFG like this one: \begin{align*} A &\to A B\\ A &\to x\\ B &\to y\\ B &\to \varepsilon \end{align*} $B$ is ...
21 views

### If you have a smallest grammar approximation, do you immediately have a CFG inference algorithm?

The smallest grammar problem is to find a single-string CFG. So given a finite list of language samples, known to all lie in some CFG, can we, using the smallest grammars (approximated) of each ...
83 views

### Give a Context Free Language, is the complement of this language always recursive(REC)?

I have seen some people make an argument that given the fact that Context Free Languages are proper subset of REC which is closed under complementation thus complement of a CFL must be in REC. I ...
923 views

### How to construct Context Free Grammar of words with equal number of 0's and 1's [duplicate]

i am trying to find a cfg for this cfl L = $\{ w \mid w \text{ has an equal number of 0's and 1's} \}$ is there a way to count the number of 0's or 1's in the string?
44 views

### Get grammar from his LALR(1) parsing table

I have a problem with this exercise. This is the LALR(1) parsing table for the grammar G. How can i get the productions of G? Thanks :)
55 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 ...
54 views

### Is the following Grammar LL(1)

I was given the following grammar $S \rightarrow S ( S ) S\mid \epsilon$ First I was asked to eliminate left recursion, yielding me the following : $S \rightarrow S'$ \$S' \rightarrow (S)...
22 views

### Are there any formal grammars describing the set of all directed graphs?

Let GRAPHS be the set of all directed graphs. Is there a set of strings STRYNGS such that there exists a bijection ...
43 views

### Can You List the Names of Some Algorithms For Determining the Intersection of Two Context Free Grammars?

Suppose we have two sets of strings XS and YS such that set XS is described by grammar GX and YS is described by grammar GY. We want an algorithm which accepts GX and Gy as inputs. The algorithm will ...
I stumbled upon the following non-linear grammar $$S \to AB$$ $$A\to aaA\mid \epsilon$$ $$B \to Bb\mid \epsilon$$ and the language generated by this non-linear grammar is {a^2nb^m : n ≥ 0, m ≥ 0} ...