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

Prove that $Y=\{w|w=t_1\#t_2\#...\#t_k\}$ is not context free

$Y=\{w|w=t_1\#t_2\#...\#t_k |t_i \in 1^*\wedge \forall_{i\neq j}t_i\neq t_j\wedge k\ge 0 \}$ Prove that $Y$ is not context free. So, let's $p$ will be pumping lemma length. $s=\#1\#11\#..\#1^{p-1}\#1^p=uvxyz$ First case: When $v$ or $y$ contains…
user220688
  • 509
1
vote
1 answer

Context-free grammar

Although the empty word $\epsilon$ is allowed in context-free grammars, it is always possible to describe any context-free language using a grammar in which the only nullable symbol is the start symbol. Transform the following grammar so that…
RA20152014
  • 11
1
vote
1 answer

Show that this CFG is ambiguous

Let $G=\langle V,T,P,S\rangle$ be the grammar defined by the productions: S-> aB|bA A->a|aS|bAA B->b|bS|aBB where $V=\{S,A,B\}$ and $T=\{a,b\}$. Show that G is ambiguous. My Approach: Left-most Derivation: S => bA =>…
geforce
  • 217
1
vote
1 answer

Context free grammar of calculator

Consider a grammar for calculator language. This language consists of all arithmetic expressions that can be evaluated by a calculator, i.e. expressions of the form expression= where "expression" is an arithmetic expression (without…
geforce
  • 217
0
votes
1 answer

Language of words $1^k$ where $k$ is not a prime

Is the language $$\{1^k:k\text{ is not a prime number}\}$$ a context free language? If, not how can I prove this using the pumping lemma for context free languages?
Talha5389
  • 103
0
votes
1 answer

Can two different rules be applied at the same step in Type 0 Grammar

As a rule in CFG, we have the liberty of applying any rule for the string S anywhere in the derivation. We can also apply different rule in one step. For example, consider the string S->0S1S and say for example that we have two rules, S->0 and S->1.…
Madhusudana
  • 308
0
votes
1 answer

Context free grammar and pumping lemma

I have a language $ L = { (b_i \# b_{i+1} ) } $ where $ b_i \ge 1 $ and $ b_i $ is binary representation of number $ i \ge 1 $ I have a word $ w = 10^N1^N1 \# 10^{N-1}10^N0$ and $ w = uvxyz $ Could someone give me a hint how to use pumping lemma ?
user157072
  • 1
  • 1
0
votes
1 answer

help to fine about CFG for $L=\{a^nb^mc^k:|n-m|=k\}$

Hi guys (and so sorry for my weak english). I have a problem about this language: $$L=\{a^nb^mc^k:|n-m|=k\}.$$ This language wants to produce some $k$ with $|n-m|$ but about another kind of this language it was my attempt: for $n-m=k$ in …
ADiNoS
  • 1
0
votes
1 answer

Describe this language that is generated by Context Free Grammar

Describe this language that is generated by a Context Free Grammar $S \to SS$ $S \to XXX$ $X \to aX \mid Xa \mid b$
Bob
  • 323
0
votes
1 answer

Chomsky Normal Form Details

I'm converting a CFG to CNF and there are some details that I'm unsure of. I know the form is A-->BC A-->a Is a transition such as S-->AA|... acceptable? Or do they have to be two different variables? Is something such as S-->aa|...…
Sams
  • 25
0
votes
1 answer

Context Free Grammar for natural numbers

this is the problem: Generate a Context Free Grammar for the language $L_1 := \{{a^nb^3c^n | n\in\mathbb N}\}$ I'm not so sure about my solution, is this correct?: $ G=(\sum,V,S,P)$ $\sum : = \{{a,b,c}\}$ $V : = \{{S,X,Y}\}$ $S : = \{{S}\}$ $P : =…
Harvat
  • 15
0
votes
1 answer

Context Free Grammar for the language?

Give CFG for $L = \{w \in \{a, b\}^{*} | n_{a}(w) \leq n_{b}(w) ≤ 2n_{a}(w)\}$, here $n_{x}(w)$ is the number of occurrences of x in w. I came up with $S-> aSb | bSa| b$ but not working as expected. Can somebody please help. Thanks in advance..!!
Vallabh Patade
  • 103
0
votes
1 answer

The necessary conditions in a proof by pumping lemma for CFG

Do we need to cover all the cases or just one of them? For instance, for $L = a^ib^jc^id^j$, the proof is uvw can't contain both a and $c$ and $b$ and $d$, but we don't cover all the cases, for instance uvw can contain as and bs, bs and cs, cs and…
george
  • 1
0
votes
3 answers

How do you show that a cfg is ambiguous?

Do we just need to show that we can get a certain string more than in 1 way? S > SSaS|SS|a|epsilon Ex: S > SSaS > aa S > SS > aa
Brian
  • 25
0
votes
1 answer

Left Recursion-Deterministic grammars

I have a question.. Is the rule $$X \to XX|a$$ a left recursive production? To make the grammar deterministic do I have to do the following changes? $$ X \to aX' ,X' \to XX'|\varnothing$$
Mary Star
  • 13,956
1 2 3
…
12 13