The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+18 votes

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

If $G$ is a context free grammar and $w$ is a string of length $l$ in $L(G)$, how long is a derivation of $w$ in $G$, if $G$ is in Chomsky normal form?

- $2l$
- $2l +1$
- $2l -1$
- $l$

+19 votes

Best answer

Chomsky Normal Form (If all of its production rules are of the form):

$A \rightarrow BC$ or

$A \rightarrow a$ or

$S \rightarrow \varepsilon$

where $A, B$ and $C$ are nonterminal symbols, $a$ is a terminal symbol ($a$ symbol that represents a constant value), $S$ is the start symbol, and $\varepsilon$ is the empty string. Also, neither $B$ nor $C$ may be the start symbol, and the third production rule can only appear if $\varepsilon$ is in $L(G)$, namely, the language produced by the context-free grammar $G$.

Applying productions of the first form will increase the number of nonterminals from $k$ to $k + 1$, since you replace one nonterminal $(-1)$ with two nonterminals $(+2)$ for a net gain of $+1$ nonterminal. Since you start with one nonterminal, this means you need to do $l - 1$ productions of the first form. You then need $l$ more of the second form to convert the nonterminals to terminals, giving a total of $l + (l - 1) = 2l - 1$ productions.

$A \rightarrow BC$ or

$A \rightarrow a$ or

$S \rightarrow \varepsilon$

where $A, B$ and $C$ are nonterminal symbols, $a$ is a terminal symbol ($a$ symbol that represents a constant value), $S$ is the start symbol, and $\varepsilon$ is the empty string. Also, neither $B$ nor $C$ may be the start symbol, and the third production rule can only appear if $\varepsilon$ is in $L(G)$, namely, the language produced by the context-free grammar $G$.

Applying productions of the first form will increase the number of nonterminals from $k$ to $k + 1$, since you replace one nonterminal $(-1)$ with two nonterminals $(+2)$ for a net gain of $+1$ nonterminal. Since you start with one nonterminal, this means you need to do $l - 1$ productions of the first form. You then need $l$ more of the second form to convert the nonterminals to terminals, giving a total of $l + (l - 1) = 2l - 1$ productions.

@Arjun @Rajarshi_Sarkar SIR

Applying productions of the first form will increase the number of nonterminals from k to k + 1,

- What is First Form Productions ?
- What is ' k ' Here ?
- Please answer this with an example

@arjun sir ,

I used to follow Mishra . It was easy to understand . And in my classnotes it is written does not have epsilon production

From spinser .

If only A -> BC and A -> a is there, i.e the language does not include empty string, then it is CRF (chomsky reduced form).

@Arjun @Kapil @pC SIR could u explain my doubt ? I too wanted to take part in the discussion :(

Applying productions of the first form will increase the number of nonterminals from k to k+1, since you replace one nonterminal (-1) with two nonterminals (+2) for a net gain of +1 nonterminal. Since you start with one nonterminal, this means you need to do l−1 productions of the first form. You then need llmore of the second form to convert the nonterminals to terminals, giving a total of l+(l−1)=2l−1productions.

Now I understand that ,

first form A->BC and second form : A->a

Let given grammer ( as expained in below answer by @pC )

S→AB

A→BC|a

B→CC|b

and input string be :w = ab

Could u explain the last paragraph ?? Like

- How the non terminals gets increased ?
- does k denote |w| ?

$S \to AB \\ \to aB \\ \to ab$.

So, derivation length is 3 for $|w|=2$.

Say if $S\to AB \\ \to ACC $

Now, the non-terminal got increased.

$k$ denote the no. of non-terminals at any step.

So, derivation length is 3 for $|w|=2$.

Say if $S\to AB \\ \to ACC $

Now, the non-terminal got increased.

$k$ denote the no. of non-terminals at any step.

Not able to follow that last paragraph :(

+4 votes

Chomsky Normal Form (If all of its production rules are of the form)

'

Source : Spinser

According to Question :

Assuming the grammer (given ) is in CNF and we need to find the length of the production .

Consider a Grammer in CNF Form

$S\rightarrow AB$

$A\rightarrow BC | a $

$B\rightarrow CC| b $

Derivation w = ab $|w|= n=2$

$S\rightarrow AB$

$S\rightarrow aB$

$S\rightarrow ab$

We took 3 derivations .

When $n=2$ Number of productions in derivation is 3 . From options $2n-1$ satisfying this . Hence **option c**

[ need @arjun Sir , to verify this ]

That need a mathematical approach . It is best described here on Problem 2.26

Yes, but in this question you cannot simply substitute the choice- because the question asks for "how long can a derivation be" which is like "maximum length of derivation". So, if you substitute the highest value choice and get "yes", then fine. Other values cannot be substituted- because we never know if they can happen for some other string.

+3 votes

**A CFG is in Chomsky normal form when every rule is of the form A → BC and A → a, where a is a terminal, and A, B, and C are variables. ****Further**** B and C are not the start variable. ****Additionally**** we permit the rule S → ε where S is the start variable.**

**if G is a context-free grammar in Chomsky normal form, and w is a string of length n ≥ 1, then any leftmost derivation of w from any variable X contains exactly 2n − 1 steps. **

https://courses.cs.washington.edu/courses/cse322/08au/lec14.pdf

https://courses.engr.illinois.edu/cs373/sp2009/lectures/old/lect_15.pdf

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.8k
- Digital Logic 2k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.8k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 940
- Others 1.2k
- Admissions 320
- Exam Queries 409
- Tier 1 Placement Questions 17
- Job Queries 52
- Projects 8

34,170 questions

40,846 answers

115,882 comments

39,703 users