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

Is it possible to create this context-free grammatic?

Is it possible to create this grammatic? $$ \left. 0^i 1^j 2^k \right| i + j \ne 2k $$ I try to create this, but I don't understand. I assume that we have to output $k$ characters '2' beforehand. But I think I'm confused. Can someone help me?
Kioshi Yamashita
  • 3
0
votes
1 answer

Convert a CFG to GNF

I have to convert the below grammar to GNF. $S \Rightarrow SA$ $A \Rightarrow aAb|cCc$ $B \Rightarrow D|ba$ $C \Rightarrow dCd| ɛ$ $D \Rightarrow De|Df|cD|c$ I have seen some examples and tutorials on the internet. In most of them, there were 3…
Aylin Naebzadeh
  • 1
0
votes
0 answers

Prove the language of equal a's and b's or b's and c's is inherently ambiguous

Question from Sipser, exercise 2.29. Prove that the language $A = \{a^ib^jc^k | i = j \text{ or } j = k \}$ is inherently ambiguous, that is, every grammar which generates $A$ is ambiguous. So the problem here appears to be the case when $i = j =…
Duncan Ramage
  • 6,928
  • 1
  • 20
  • 38
0
votes
2 answers

Give a context-free grammar

I'm struggling to understand how to construct a context-free grammar for the following language. $\{b^nw|w∈\{a,b\}^∗,|w|=n,n≥0\}$ The thing that is confusing me is the beginning of the statement. I would understand a statement like the one below to…
confusedman
  • 1
0
votes
0 answers

How to define the language generated by context-free grammar?

I have a context-free grammar defined: S -> aS, S -> Sb, S -> a I thouht that correct answer would be: L(G) = {aab}, because: S -> aS -:> aSb -> aab but isn't. Why, and what is correct answer?
Mike
  • 1
0
votes
1 answer

Show that $L=\{a^i b^j c^k\,:\, i < j < k\}$ is not context free

I am looking to show that $L=\{a^i b^j c^k\,:\, i < j < k\}$ is not context free. So I suppose that it is a context free language and use the pumping lemma. Let $n$ be the parameter of the lemma and define $z=a^nb^{n+1}c^{n+2}$. We can so write…
Frederick Manfred
  • 901
0
votes
0 answers

Is the language {a,b,c} which words are divisible by 4 and the word start and ends with same letters is context free?

is the language above the {a,b,c} alphabet composed of words of length divisible by 4 starting and ending with the same letter context-free? I tried doing it with Pumping lemma but im not sure if i did it right. So f.e i choosed word z =…
dissu1337
  • 1
0
votes
1 answer

Context free grammar for $=\left\{^n ^m\mid0<≤≤4+3 \right\}$

I tried to start writing the grammar but was only successful when $m = n$: $$S \to ab \, |\, aSb$$ As for the rest, I can not find out about the legality I would be happy if you could help me.
Lior Atiya
  • 11
0
votes
1 answer

Find a CFG for $\{a^n b^m c^k \mid m=n+k\}$

I am trying to build the CFG to $\{a^n b^m c^k \mid m=n+k\}$ but does not working. I tried $S \to aSc$, $S \to S_1$, $S \to \epsilon$, $S_1 \to bS_1c$, $S_1 \to \epsilon$ but it does not work.
Vagner Wentz
  • 115
0
votes
1 answer

Is the grammar for the language $L = \{ a^nb^mc^n \mid n,m \geqslant 0 \}$ correct?

I was doing this grammar. The language $L = \{ a^nb^mc^n \mid n,m \geqslant 0 \}$ I wanted to know if it is correct or not. This is my solution $S \to aSc\mid B \mid e$ $B \to bB \mid e$
ANDREA LUIGI PALLADINO
  • 25
  • 3
0
votes
1 answer

Construct CFG for the complement of a language

Construct the CFG for the complement of $$L = \{ a^ib^jc^k \mid i \ge 0, j \ge 0, k \ge 0 \text{ and } i \ge j + k \}$$ I tried to write the complement as the union of $L = \{ a^ib^jc^k \mid i \ge 0, j \ge 0, k \ge 0 \text{ and } i < j + k \}$ and…
newbie
  • 65
0
votes
1 answer

Find a context-free grammar for $L = \{a^lb^n c^m |l, n, m ∈ \mathcal{N} + ∧ ((l ≥ n) ∨ (l ≥ m))\}$

I have to find a constext-free grammar for the language $L = \{a^lb^n c^m |l, n, m ∈ \mathcal{N} + ∧ ((l ≥ n) ∨ (l ≥ m))\}$. However, it seems hard to see where to start with the condition $((l ≥ n) ∨ (l ≥ m))$. All I know is we can't have strictly…
Robert
  • 19
0
votes
1 answer

Why is $T \Rightarrow T$ false, but $T \stackrel{*}{\Rightarrow} T$ true? I'm not sure how to derived this.

R -> XRX | S S -> aTb | bTa T -> XTX | X | ε (empty string) X -> a | b $T \Rightarrow T$ $T \stackrel{*}{\Rightarrow} T$ I know the first one is false since you cannot derived it to T but for the second one my friend said it is true while I…
Qezzz
  • 3
0
votes
1 answer

Proving that a particular CFG grammar generates language L

$$L=\left\{w\in\{x,y\}^*\mid N(y)=2N(x)\right\}$$ and $G$ is $$S\to yySx\mid ySxSy\mid xSyy\mid SS\mid\epsilon$$ I need to proof that the grammar generates this language. I know that I need to use induction to prove it, but I can't follow…
ministrelia
  • 13
0
votes
0 answers

How do you express symbollically that an equation doesn't have solution over the reals?

This is a really quick doubt, i'm just curious about how it will be. Imagine an equation like $\cos(x)=\sqrt{-1}$, it obviously doesn't have solutions over the reals, how do I express it symbollically? (e.g using mathematical language, as $\exists$…
Xetrez
  • 358
1 2 3
…
12 13