Question

3a) Let ?={????:0≤?≤?}. How many of the following strings are in ?∗?

?,??????,????,???,????,????,?????,????

3

4

5

6

b)

Let ? be any NFA with a single final state. If we convert ? into a right-linear grammar ?, the number of production rules in ? will be equal to

number of transitions in ?

number of states in ? plus 1

number of states in ?

number of transitions in ? plus 1

Answer 1

3a)The answer of this question is 3.

Description of the Answer: As the question is given the automata accepts the string a_ib_j if 0<=i<=j.So,clearly the string will be starting from a or b .If b comes once a can't come,as the rule given and number of a must be less than or equal to the number of b .Check the answers now and match the follwoing criterias.

Lambda : in which number of a and b is 0.So,obviously it will be accepted.

aaaaab can't be accepted as number of a is not less than number of b.

and after b , a can't come so we can eliminate abab,babb,baba,abaab.

now for the others bbb,aabb ,these are obviously valid and will be accepted, as number of a is less than or equal to number of b.

so the correct answer will be 3(lambda,bbb,aabb).

b)The answer of this question is option no 4,number of transition in M plus 1.

Description:The right linear grammer is one type of grammer where A->aB means from A state by giving terminal a we can reach to a state B.For the NFA (Nondeterministic Finite Automaton) as the transition given we can easily convert it into right linear grammer .We will put the statring state first and from this then terminal symbol on the right and after that the destination state.Let me give you one example:bBut while we are converting from NFA to right linear grammer the final state will get a production of epsilon.As this is a final state the grammer indicates where to stop.That is why As per the question given the number of final state is 1.So ,from NFA the right linear grammer will have excess production rules by 1 only.That gives 4th as the right answer.The number of productions in right linear grammer will be number of productions in the NFA plus 1 as the number of final state is 1.One extra final state to epsilon production.