Questions tagged [context-free]

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

1,154 questions
Filter by
Sorted by
Tagged with
68 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?
77 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?
40 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:...
58 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 ...
51 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 ...
39 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 ...
41 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 ...
138 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 ...
43 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 ...
43 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 ...
59 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 ...
48 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 ...
38 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 ...
40 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,...
50 views

42 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 ...
61 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 ...
409 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?
41 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 :)
46 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 ...
49 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)...
21 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 ...
41 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} ...