Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [context-free-grammar]

Context-free grammars give a set of rules for generating formal languages. The formal languages generated by a context-free grammar are known as context-free languages.

Context-free grammars (CFGs) were introduced by Noam Chomsky in an attempt to classify formal languages. CFGs are type-2 grammars in the Chomsky hierarchy and generate what is known as context-free languages.

Formally, CFGs consists of a set $V$ of variables, an alphabet $\Sigma$, a set of production rules $R$ and a start symbol $S \in V$.

As an example, the following CFG generates the language of all strings starting with $1$ over the alphabet $\{1,0\}$. The start symbol is $S$.

$$S \rightarrow 1B$$

$$B \rightarrow 1B \; | \; 0B \; | \; 1 \; | \; 0$$

Here the arrow means that the variable on the left-hand side can be replaced by any of the expressions on the right-hand side, where different expressions are separated by a $|$.

To derive the string $1101$ from the previous CFG, we can give the following derivation, starting with the start symbol $S$.

$$S \Rightarrow 1B \Rightarrow 11B \Rightarrow 110B \Rightarrow 1101$$

980 questions
1
vote
1 answer

Proving the context-free languages are closed under reverse

In the book I am reading it is stated that if $L$ is a context-free language then so is $L^{R}$(where $L^{R}:=\{w^{R}:w\in L\}$, example: $(ab)^{R}=ba$). This claim has been proven in the text using Chomsky normal form and hence it $\epsilon\in L$…
Belgi
  • 23,150
1
vote
2 answers

Prove $\{0,1\}^* -\{0^i 1^i\mid i \ge 0\}$ is context free?

Is the only way to prove that this language is context-free to construct a Context-Free Grammar that accepts it? If so any hints on how to get started?
Takkun
  • 433
1
vote
1 answer

Context Free Diagram - Unequal a's and b's and c's

$$L=\{a^nb^mc^k:n≠m+k\}$$ I need a CFG for $L$. I believe I've got it down, but I would like any feedback if there is a better way of doing this one, or if I'm missing something. $$\begin{align*} S&\to A\mid Xc\mid Yb\\ A&\to a\mid aA\mid aAYb\mid…
Kevin Robles
  • 13
1
vote
1 answer

Constructing CFG for $L=\{a^ib^jc^i,\ i,j\ge 0\}$

I'm trying to construct a grammar for the following language $$L=\{a^ib^jc^i,\ i,j\ge 0\}$$ My try: $$G=\left(V=\{S,X,Y\},\Sigma=\{a,b,c\},R,S\right)$$ where the rules are \begin{align*}S&\to X|Y \\ X&\to aXc|Y\\Y&\to bY|\varepsilon\end{align*} Is…
Galc127
  • 4,451
1
vote
3 answers

context free grammar accepted and generated language problems

I'm having problems completing the following questions, I am able to attempt them but don't know if they are correct. Any help would be much appreciated. Answer the following questions for a context free grammar $G=(N,\Sigma,P,S)$, where $N,\Sigma,…
dmnte
  • 257
1
vote
0 answers

Context free grammar L={$a^{m}$ $b^{n}$ $c^{k}$| n,m,k >= 0, n>= m+k}

Write a context free grammar for the following: $$L=\{a^{m}b^{n}c^{k}\mid n,m,k \ge 0, n\ge m+k\}$$ I am having some trouble writing the above cfg from the language. So far I have: $$\begin{align*} S&\to S_1S_2S_3\\ S_1&\to aS_1b\\ S_1&\to…
ImTheRealOne
  • 11
1
vote
1 answer

Context free Grammar : three small exercices

Hi everybody I want to submit you my work I did on some works and receiving also some help :) Thank you a lot : so here the exercices on which I worked : Ex 1: Prove that the language : $L=\{w\in\{a,b,c\}^*|n_a(w)=n_b(w)=n_c(w)\}$ isn't context…
Studentin
  • 11
1
vote
0 answers

What happens when all productions in a grammar are useless?

I have this grammar, and I've been asked to eliminate all useless productions. S-> aS | AB A-> bA B-> AA Now it's pretty easy to see that every production is useless because none of them produce terminal strings. So does this just result in an…
Talen Kylon
  • 563
1
vote
2 answers

Are these two grammars equivalent?

Let's say I have the following two grammars, and V is the start symbol. $V \to aVb | ab | \Lambda$ and $V \to aTb | ab$ $T \to aTb | \Lambda$ I refute that these are equivalent because with the first grammar we are able to print out an empty…
Julian D
  • 13
1
vote
2 answers

Context free grammar problems

Im having trouble doing the following context free grammer questions, the book im using doesnt cover this in the same way so im having trouble just understanding the questions, let alone doing them. Can anyone clarify the meanings and maybe hint to…
dmnte
  • 257
1
vote
1 answer

Creating a CFL - based off unknown Regular language

Suppose $A\subseteq\Sigma^{\ast}$ is a regular language. Let $B=\{xy^R:x,y\in\Sigma^* , |x|=|y|, x \ XOR \ y \in A\}$ Prove that B is context free. I am struggling with understanding B. My only thought on how to start, is to assume A is in Chomsky…
sci1991
  • 43
1
vote
1 answer

What does this CFG accept?

I am not sure what this language accepts: $S \to 01S2A\,|\,\epsilon$ $A \to 1A\,|\,1$ I thought something like: $(01)^i(21)^i1^n$ But then I didn't know how to handle all the 1's that can come after each 2.
Lee
  • 811
1
vote
0 answers

Check if $L\in CFG$ then $L'\in CFG$

Check if $L\in CFG$ then $L'\in CFG$ $L'=\{w|ww^R\in L\}$ So, I show counterexample. Let $L=\{a^ib^ja^ib^l|i,j,l \ge 0\}\cdot \{b^za^xb^za^y|x,y,z\ge 0\} = \{a^ib^ja^ib^lb^za^xb^za^y|x,i,j,l,y,z\ge 0\}$ Then $L\in CFG$ What about word $ww^r\in L$ ? …
user220688
  • 509
1
vote
0 answers

prove that language is non-context free

Prove that $A=\{wtw^R|w,t\in \{0,1\}^*\wedge |w|=|t|\}\notin CFG$ I use pumping lemma: Let $p$ will be length of pumping.Given $s=1^p0^p1^p=uvxyz $ We know, that (because of the fact that $|vxy|\le p$): $vxy\in 1^k0^l$ $vxy\in 0^p$ $vxy\in…
user220688
  • 509
1
vote
2 answers

Prove that language is context-free $C=\{x\#y \mid x,y\in \{a,b\}^*\wedge x\neq y\}$

Prove that this language is context-free: $C=\{x\#y|x,y\in \{a,b\}^*\wedge x\neq y\}$. I try to construct a grammar: $S\rightarrow C_a\#C_b|C_b\#C_a$ $C_a\rightarrow XC_aX|a$ $C_b\rightarrow XC_bX|b$ $X\rightarrow a|b$ Is it good ? I can try to…
user220688
  • 509
1 2 3
…
12 13