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

Context-Free Grammar for {w| w contains at least as many 0's as 1's and |w| >= 2} over the alphabet {0,1}.

I have first created the following CFG for the same number of 0's and 1's: S → S0S1S | S1S0S | ε To create more 0's than 1's, do I need to introduce a new variable such as the following? S → SAS1S | S1SAS | 0A A → 0A | 0 But it's not working!
afarin af
  • 1
0
votes
1 answer

Ambiguity in a grammar and getting rid of it

I'm trying to figure out how I can change my grammar to get rid of the ambiguity but I'm having a hard time figuring it out, unfortunately I haven't been able to find an example that's close enough to my problem either. The grammar: $S\rightarrow…
AFC
  • 383
0
votes
1 answer

If L* is context-free, is L context-free as well?

I know CFL in closed under Closure, but don't know how to prove it back. I try to construct a CFG for L* such as S->ε|AS and say since L* in a context-free language, there must exist a method to build grammar A. So then we can use A to construct…
Tawcher Bro
  • 41
0
votes
0 answers

What is the minimum and maximum number of productions in Chomsky and Greibach Normal forms?

How many min and max number of productions will be required in Chomsky Normal Form(CNF) and Greibach Normal From(GNF) each if string length = n ? I've heard somewhere that in GNF, minimum and max productions both are "n". Unable to understand this…
SpawN
  • 67
0
votes
0 answers

Intersection and union between two context-free languages

It has been difficult for me to demonstrate these two exercises, I hope they can help me. this is the problem I think the union is a free-context language.
purplewave
  • 1
0
votes
2 answers

CF grammar for a Language.

I am trying to formulate a CF grammar for a language of alphabet { a , b, c} with a condition that the number of characters a standing anywhere in the word before this given c larger by 3 than the double of the number of characters b standing…
MaJou
  • 3
0
votes
1 answer

Find context free grammar and prove its correctness

Find context free grammar for a given language and prove its correctness: a) $\left\{ a^ib^ja^k : i\neq j \ \vee \ j\neq k \right\}$ b) $\left\{ w\in \left\{a,b\right\}^* : \#_a(w)=2 \cdot \#_b(w) \right\}$ c) set of all words $w\in \left\{ a,b…
xan
  • 2,053
0
votes
1 answer

Context free grammar to language

Suppose we have $G(V,Σ, R, S)$ where $$\begin{array}{ll} V & = \{a,b,A,B,S\}\\ Σ & = \{a,b\}\\ R &= \left\{ \begin{array}{rl} S &→ abA,\\ S&→B,\\ S&→baB,\\ S&→e,\\ A&→bS,\\ B& →aS,\\ A&→b \end{array}\right\}\end{array}$$ What is language $L(G)$ ?…
Alihuseyn
  • 1
0
votes
1 answer

Context-free grammars a*(ba*ba*)*

I'm having trouble to find context free grammars which generate following languages a* (ba* ba*)* * means zero to infinite My solution is : S--> aS | bS | ε Is that right? Accroding to the comment I modify my solution S → AbAbA | ε A → aA | ε or S…
user9976577
  • 3
0
votes
2 answers

Context Free Grammar for $L = \{0^n w 1^n \mid n \ge 0, w \in \{0, 1\}^*\}$

Title says it all. I'm trying to make sure I have the correct CFG for $L$ before I start converting it to GNF. I don't want to post my idea yet, as I don't want it to influence any of the replies. Again, I need a CFG for $$L = \left\{0^n w 1^n \mid…
The Rationalist
  • 115
  • 4
0
votes
0 answers

$L_2$ is a set of all words where $w$ is an element of $A^*$ such that $w$ is a palindrome

I am not really good at generating grammars, because I find it very hard to come up with rules. However, after a lot of trial and error, this is what I could generate: A={a,b} Vt={a,b} Vn={S,A,B} R= S->BS S->AS S->e A->a B->b was this the correct…
koby
  • 47
0
votes
0 answers

Proof of a non context free language

I am trying to prove that $$\{u\#v\,|\,u,v\in\{0,1\}^∗ \text{and }u \text{ is a substring of }v\}$$ is not context free. Is it possible for a subset of a non-context free language to be context-free?
Aimal Mirza
  • 1
0
votes
1 answer

Finding a context-free grammar for $a^i b^j : 2i < j$

So I have a question: Give a CFG for $a^i b^j : 2i < j$. And this is my approach: $$S \to AB$$ $$A \to aAb | e$$ $$B \to b | bB$$ Thanks, a confirmation, or correction, along with how you tested (and tips for testing future problems of mine) will…
Gaak
  • 221
0
votes
0 answers

Is $a^j b^j c^k$ context free?

is the language $$\{a^j b^j c^k\; : \;(j = 2 \ OR\ j=k+i)\ AND\; i, k \gt 0\}$$ context free? if $j=2$ only I would say yes but when I add the other condition ($j=k+i$) if I use pumping lemma I get stuck. On the case $j=k+i$ I can rewrite the string…
vin2098
  • 1
  • 1
0
votes
1 answer

Provide a grammar for the language: $a^ib^jc^{i+j}:i,j \geq 0$

I am trying to provide a grammar for the above language, but keep running into the same issue. So far I have this: $S \rightarrow AB | \epsilon$ $A \rightarrow aAc | \epsilon$ $B \rightarrow bBc | \epsilon$ but these productions produce words like…
Ryan Gomez
  • 5
1 2 3
…
12 13