Scribd
Upload
15 views2 pages

Chapter-2 Language Question Rules

The document discusses methods for calculating the number of words in the language S* of varying lengths, using different approaches. Approach 1 employs a formula based on independent choices, while Approach 2 utilizes a recursive function that resembles the Fibonacci series for complex sets. Approach 3 suggests manual calculation for simpler sets, providing examples for clarity.

Uploaded by

mdyenasif
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
15 views2 pages

Chapter-2 Language Question Rules

The document discusses methods for calculating the number of words in the language S* of varying lengths, using different approaches. Approach 1 employs a formula based on independent choices, while Approach 2 utilizes a recursive function that resembles the Fibonacci series for complex sets. Approach 3 suggests manual calculation for simpler sets, providing examples for clarity.

Uploaded by

mdyenasif
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Types of Questions and Their

Solving Techniques
Consider the language S*, where S = {any alphabets}.
How many words does this language have of length 2? of
length 3? of
length n?

Solution Approaches :

Approach 1 :
Formula : number of choices ^ (length of the word asked) …. NOTE : ONLY
WORKS FOR INDEPENDENT CHOICES e.g S = {a,b} or S = {a,c,v,b} etc… each
position in the length has its own independent choice of alphabet. If we have
complex sets then go for the 2nd approach.

Approach 2 :
For example we have the alphabet set S = {ab, b} then we calculate the function of
word ending at both of these words….

Function 1 : words ending with ab.


If we subtract ab from that word, then the length of the word would become (n-2).
Considering n (total length).
Function : A(n-2)

similarly ,
Function 2 : words ending with b.
If we subtract b from that word, then the length of the word would become (n-1).
Considering n (total length).
Function : A(n-1)

Hence the total number of words from the alphabet set {ab,b} would be sum of both
the functions : A(n) = A(n-1) + A(n-2)..... {which is luckily fibonacci series}
Provided A(0) = 1 and A(n) = 0 if n<0.
Calculating A(1) = A(0) + A(-1) = 1
A(2) = A(1) + A(0) = 2
A(3) = A(2) + A(1) = 3
A(4) = A(3) + A(2) = 5
A(5) = A(4) + A(3) = 8
….
A(n) represents the total number of words of length ‘n’.

NOTE::
(if this was not a fibonacci series we would calculate values recursively from the
base values of A(0) = 1 and establish values up from this point).

Approach 3 :
Manual Calculation.
For example S = {a,b}... we have to find words of length 2 …
We can simply calculate manually aa,bb,ab,ba … total 4 words.

You might also like