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

How to represent the "power of" symbol in context free grammar?

I have to find the CFG for the following langage $$L={w|w=a^ib^ja^{i+j},i,j∈N}$$ Her is my solution but I am not completely sure about it : \begin{align*} K &-> ε\\ K &-> bK\\ S &-> ε\\ S &-> aS\\ S &-> aSbKa\\ \end{align*} I don't know how to…
Revolucion for Monica
  • 1,511
2
votes
1 answer

Is the string that is not the concatenation of a single string twice context free?

This language would not contain strings like catcat, zzzz, and hihi, but would contain strings like cat, mrbean, and moose. I tried using the pumping lemma, but it seems that this language can be pumped... however, constructing a grammar for this…
John Hoffman
  • 2,734
2
votes
2 answers

correct disambiguation of a grammar?

So I'm given the grammar $$P ::= id | P ∨ P | P ∧ P | ¬P | (P)$$ $$id ::= p | q | r | s$$ and was asked to rewrite it as unambiguous. The solution says it is $$P ::= P ∨ Q | P ∧ Q | Q$$ $$Q ::= id | ¬Q | (P)$$ $$id ::= p | q | r | s$$ but using the…
greenteam
  • 333
2
votes
2 answers

Prove that if $\mathcal L$ is context-free so $\mathcal L_{\text{even}}$ is context-free

Let $\mathcal L$ be a language. Denote by $\mathcal L_{\text{even}}$ the language consisting of all words in $\mathcal L$ whose length is even. Prove that if $\mathcal L$ is context-free over the alphabet $\{0,1\}$ then $\mathcal L_{\text{even}}$…
user306663
2
votes
1 answer

Context-free language, computability theory

I want to show that the following language is not context-free: $$\{a^nb^m\mid0\leq n\leq m^2\}$$ I tried the word $w=a^kb^k$, but it does not work, because I can't show that for every possible partition $w=uvxyz$ (with the conditions of the…
ChamDao
  • 21
2
votes
0 answers

Context-Free Grammar production rules and terminals

For a context-free grammar G = (V,T,S,P) If one production rule of G is A -> nBC where n ∈ T*, does it mean that the production rule of the form A -> BC is also allowed? Since n ∈ T*, can n be empty due to the Kleene star on T (set of terminals)?
stevetronix
  • 433
2
votes
1 answer

Prove or disprove: $L^2$ context free implies $L$ is context free.

Clearly we have to disprove this. But I am finding it hard to prove it. I was trying in following way: Considering any non context free language $L$. I was trying to prove that $L^2$ is context free which will contradict given statement. But I don't…
Rohit
  • 21
1
vote
0 answers

Converting a long CFG to Chomsky Normal Form

I know there's a lot of examples on here, although I just cant seem to get this one, it seems significantly harder than any examples I've seen, the grammar is: S-> ABAC | BaA A-> Aa | BAbC | lambda B-> bB | aBaC | lambda C-> a|b now by removing…
drocktapiff
  • 55
1
vote
2 answers

Context free grammar for a specific context-free language

Problem $L = \{ w \in \{a, b\}^* : n(a) \neq 2 \cdot n(b)\}$ This can be done easily with NPDA, but I couldn't find a way to make it work with CFG. My idea was to break it into 2 cases: $n(a) > 2 \cdot n(b)$ or $n(a) < 2 \cdot n(b)$. I first try to…
roxrook
  • 12,081
1
vote
1 answer

CFG for $a^ib^jc^k | i\neq j\ or\ j\neq k$

This is my Homework problem. Can someone please help me out! Find CFG(Context Free Grammar) for the language L={$a^ib^jc^k | i\neq j\ or\ j\neq k$}.
Madhusudana
  • 308
1
vote
1 answer

How come this grammar is unambiguous?

Equivalent unambiguous grammar: \begin{align} S &\rightarrow ABA|AB|BA|A|B \\ A &\rightarrow aA | a \\ B &\rightarrow aB|b \end{align} an unambiguous language has only one parse tree, but there are two parse trees for the grammar above: $ABA >…
george
  • 11
1
vote
1 answer

How is this derivation possible in a context-free grammar?

Suppose we have the rules: $R \rightarrow XRX | S$ $S \rightarrow aTb | bTa$ $T \rightarrow XTX | X | \epsilon$ $X \rightarrow a | b$. My textbook says that $T \stackrel{*}\implies T$ is possible. Could this be a mistake because I am almost certain…
Joseph DiNatale
  • 2,845
  • 22
  • 36
1
vote
1 answer

Creating the production for a CFG

I have to create the productions for a CFG that follows $$\{a^ib^jc^k : j = i + k\}$$ I can get close to the answer. I found $$\begin{align*} &A\to aAb \mid B\\ &B\to bBc \mid \epsilon \end{align*}$$ but that allows c's in the wrong place. I need…
Sams
  • 25
1
vote
1 answer

Producing CFG for a language

The language of palindromes over {a,b} whose length is a multiple of 3, I am clueless as to how you would attempt this.
tarantino
  • 21
1
vote
2 answers

Express $\{w\mid w \text{ contains at least two } 1\text{'s}\}$ in CFG

Let $\Sigma = {0, 1}$. Write CFG that generates the following language {w | w contains at least two 1’s} I'm not really sure how to write a CFG that generates a language, so this is my attempt... S-> A1A1A A->0A1|1A0|AA|$\epsilon$ I'm not sure…
Sarah
  • 263
1 2
3
…
12 13