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
0
votes
1 answer

CFG production rules for multiple CFG's

I have the following 2 part question of which I can do the first part but am having trouble understanding the question for the second part. The first part asked for the production rules for $L_1=(a^nb^n |n\geq0)$, $P_1 = (S_1 \rightarrow…
dmnte
  • 257
0
votes
1 answer

Context Free Grammar number of b's < double the number of a's

I need to build a context-free grammar for $\{a^ib^j \mid j < 2i\}$ So far I have $$\begin{align*} &S\to aSB\mid ab\mid a\\ &B\to bb\mid b\mid\varepsilon \end{align*}$$
Tammy
  • 21
0
votes
1 answer

Context free grammar over { a^n * b^(n+3) | n >= 0 }

Context free grammar over { a^n * b^(n+3) | n >= 0 } So far I have this, but I don't think it's entirely correct S --> aSbS | TbTbTb T --> aTbT | lambda Is the aSbS even necessary? SOLUTION S --> aSb | Tbbb T --> aTb | lambda
hey zuse
  • 3
0
votes
1 answer

How to write a grammar that accepts the language formed by strings $e^{3n} f g^{2n} h$?

$e^{3n}\: f \: g^{2n}\: h$ n ∈ ℕ∪{0} For Example: fh eeefggh eeeeeefggggh I am stuck at the $e^{3n}$ and $g^{2n}$ part. This is what I have so far: S→EfGh E→eE∣ϵ G→gG∣ϵ Please correct me if I am wrong. Thanks
TheDoctor
  • 139
0
votes
0 answers

When eliminating the lambda expressions from this grammar, are we missing a production?

I'm working on converting this grammar to CNF (Chomsky Normal Form). S-> abAB A-> bAB | lambda B-> BAa | A | lambda So I started off by eliminating the lambda productions, and in doing so I got this: S-> abAB | abB | abA | ab A-> bAB | bA | bB …
Talen Kylon
  • 563
0
votes
1 answer

What is meant by S -> SS in a CFG?

In the following CFG, S -> aSb | SS | ε I'm really confused with what happens with the rule S -> SS. In my textbook it explains that that the grammar generates the strings aabb, abab, and aababb. How does it generate each of these strings? What is…
amosq
  • 3
0
votes
1 answer

Find a grammar that generates this language.

I have a homework problem that I'm working through: $L = {ww^R : w \in \{a,b\}^+}$ So I get the following: $S \to aSa | bSb | \Lambda$ I am confused about the $\{a, b\}^+$, doesn't this mean that our alphabet cannot include $\Lambda$? If so, how do…
Julian D
  • 13
0
votes
1 answer

Prove that language is non-context free $L=\{a^{n^2}b^n|n\ge 0\}$

$\{a^{n^2}b^n|n\ge 0\}$ Is there any way to solve it beyond Pumping lemma ?
user220688
  • 509
0
votes
1 answer

How to show that there is an equivalent context-free grammar

How can I show that for every context free grammar G, there is an equivalent context-free grammar that has production rules with these forms only: $C→x $WV or $C → λ$, where $x$ is a terminal and $W$ and $V$ are variables. The permitted rules look…
stevetronix
  • 433
0
votes
1 answer

show that $L = \{a^n b^m | m\neq n\}$ is context free language

show that $L = \{a^n b^m | m\neq n\}$ is context free language using closure under union My attempt is show L1 = a^n b^m n>m is context free and show L2 = a^n b^m n less than m is also context free Then we know L1 U L2 = {a^n b^m m!=n }is also…
user2247155
  • 3
0
votes
1 answer

Check if languages $K$ and $L$ are non-context free

$K = \{a^kba^lba^n|kk+l=n\} $ $L=\{a^kba^lba^n|kl=n\} $ Firstly, let's consider language $K$. I use pumping lemma to show that $K\notin CFG$. Let $s=a^pba^pba^{2p}=uvxyz$ Thanks to pumping lemma: $$(1)|vy|>0$$$$(2)|vxy|\le p$$$$(3)\forall_{i\ge…
user220688
  • 509
0
votes
1 answer

Syntaxes one can describe using BNF?

How can one tell if certain syntax is describable by BNF? Is it anything i can describe with a context free grammar? So are programming languages like C,java.. describable by BNF? or does it depend on the language? What about something like the…
Bilal27
  • 27
0
votes
3 answers

prove that language is not free context

$F=\{\,a^ib^j\mid i=kj\text{ for some $k>0$}\,\}$ Prove that this language is not context free. The only thing that comes to my mind is pumping lemma; Let $p$ be the pumping length. Given $s=a^{pk}b^p =uvxyz$ for some positive $k$. When $v$ or…
user220688
  • 509
0
votes
2 answers

prove that set of palindroms such that $\#_0(w)=\#_1(w)$ is not CFG

$B$ - set of palindroms such that number of $1s$ is equal to number of $0s$. Every palindrom $\in \{0,1\}^*$ And my task let me that $B$ is not CFG. But I don't agree with it. Because of the fact that $\#_0(w)=\#_1(w)$ I conlude that $B$ is set of…
user220688
  • 509
0
votes
1 answer

Find CFG for language $\#_a(w) = 2\#_b(w)$

$L=\{w\in (a+b)^*:\#_a(w) = 2\#_b(w)\}$ I can think grammar: $S\rightarrow abSa\ |\ aaSb\ |\ baSa\ |\ bSaa\ |\ aSba\ |\ aSab\ |\ SS$ But I couldn't prove that it is full (generates all words). When it comes to corectness: Induction with length. But…
user220688
  • 509
1 2 3
…
12
13