Blog: CS402 Subjective Paper 3

Question: 1                 (Marks 1)
Can you say that string of 0’s whose length is a perfect square is not regular?


Question: 2                (Marks 2)
Is the following an FA or TM?


Question: 3                 (Marks 2)
If L is the language that accept even length strings then what strings will Lc accept?


Question: 4                 (Marks 3)
Define Myhill Nerode theorem


Question: 5                 (Marks 3)
If L1,L2 and L3 be any three finite languages over Sigma = {a,b}, then how will be
(L1 INTERSECTION L2) Union (L2 INTERSECTION L3) ≠ Ø


Question: 6                 (Marks 3)
How you differentiate between wanted and unwanted branches while deriving a string from in the context of CFG?


Question: 7                 (Marks 5)
What is the difference between concatenation and intersection of two FAs and union and addition of two FAs?


Question: 8                 (Marks 5)
Use pumping lemma II to show that following language is not regular.
L = {an2 ; n =1,2,3,4…}


Question: 9                (Marks 10)
Draw Moore Machine equivalent to the following Mealy Machine.


Question: 10                (Marks 10)
Write CFG of the following PDA. Also write the stack alphabet and tape alphabet.