There is a thin, long and hollow fibre with a virus in the centre. The virus occasionally becomes active and secretes some side products. The fibre is so thin that new side products secreted by the virus push the old products along the fibre towards its ends. The possible actions of the virus are as follows 
(a) Produce an acid molecule to its left and a base molecule to its right.
(b) Produce a base molecule to its left and an acid molecule to its right.
(c) Divide into two viruses, each of which continues to behave like its ancestor.
(d) Die. 
You are given a sequence of acid and base molecules from one end of the fibre to the other end.The actions of the virus can be represented using a grammar, using V as the virus, a and b as the acid and base molecules respectively.
The grammar is:

(A) Regular

(B) Context-free but not regular

(C) Context-sensitive but not context-free

(D) None

Hint: 

Responses

sumitverma's picture

The actions of the virus can be represented using the following context-free grammar: where V is the virus, a and b are acid and base molecules respectively.
V → aV b
V → bV a
V → V V
V → ε
The language of the above grammar is the set of strings consisting of equal number of a’s and b’s.
A sequence of acid and base molecules is just a string over {a, b}. To check if a single virus could have produced the sequence, you can use CYK algorithm to check membership in the above context-free grammar.

Did not found what you are looking for, Ask your doubt or Help by your contribution

Enter your search keyword:

Search form

Wait!

Here is a chance to join biggest community of technical Students,
Tutors with FREE learning resources and so much more.
It takes less then 60 seconds.