Hello, I was asked to think about the following problem: Suppose we have a CFG i

Question

Hello, I was asked to think about the following problem:

Suppose we have a CFG in Chomsky Normal Form, lets call it H, and it contains x variables. How can you show that if H generates some string with derivation having atleast 2^x steps, that the language of H is infinite.

I am thinking that it has something to do with the fact that a Chompsky Normal Form can have as many terminals pointing to variables as it needs, but I am not entirely sure how to think about this problem. Any and all help would be greatly appreciated!

Explanation / Answer

Its pretty simple:

In order to generate a string of n length CNF requires 2*n-1 steps. How?

S->AB

A->BC

B->CD

C->c

D->d

S->AB->(BC)B->(CD)CB->(CD)C(CD) in 1+1+1+1 steps

i.e it requires 4 steps to go to 5 non terminals

Now, it requires 5 steps to transfer nonterminals to terminals

i.e.

CDCCD->cdccd 5 steps for each non terminal

so total 2*n-1 steps

n-1 steps to make n nonterminals

n steps to make n terminals from n nonterminals

Now,

If "H generates some string with derivation having atleast 2^x steps"

then it can take more than 2^x steps i.e. it can take an infinite number of steps.

Increasing number of steps will simply increase the length of strings produce,

Hence H is capable of producing infinte number of strings with different length,

Hence Language of H must be infinte.

If it would had been at most 2^x steps then we are putting a bound

on the length of string that this CNF is capable of producing,

which results in finite language

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.