 |
|
#1
12-01-2011, 07:23 PM
|
||||
|
||||
cs402 subjective for midterm 2011
Question No: 27 ( Marks: 2 )
Diffrentiate between Regular and Non regular languages? Ans:The main difference between regular and non regular language are as: 1. The regular language is that language which can be expressed by RE is known as regular language whereas any language which can not be expressed by RE is known as non regular language. Question No: 28 ( Marks: 2 ) What is meant by a "Transition" in FA? Question No: 29 ( Marks: 2 ) What are the halt states of PDAs? Ans: There are some halts states in PDA which are as: Accept or reject stat is also halt state. Reject state is like dead non final state. Accept state is like final state. Question No: 30 ( Marks: 2 ) Identify the null productions and nullable productions from the following CFG: S -> ABAB A -> a | /\ B-> b | /\ Question No: 31 ( Marks: 3 ) Describe the POP operation and draw symbol for POP state in context of Push down stack. Question No: 32 ( Marks: 3 ) What does the the following tape of turing machine show? Ans: Arbitrary Summary Table: The arbitrary summary table shows the trip from READ9 to READ3 does not pop one letter form the STACK it adds two letters to the STACK. Row11 can be concatenated with some other net style sentences e.g. row11 net(READ3, READ7, a)Net(READ7, READ1, b)Net(READ1, READ8, b) it gives the non terminal Net(READ9, READ8, b), The whole process can be written as: Net(READ9, READ8, b) ?Row11Net(READ3, READ7,a) Net(READ7, READ1, b)Net(READ1, READ8, b) This will be a production in the CFG of the corresponding row language. Question No: 33 ( Marks: 3 ) Find Pref (Q in R) for: Q = {10, 11, 00, 010} R = {01001, 10010, 0110, 10101, 01100, 001010} Question No: 34 ( Marks: 5 ) Consider the Context Free Grammar (CFG) S à 0AS | 0 A à S1A | SS | 1a Show that the word 0000100 can be generated by this CFG by showing the whole derivation starting from S Question No: 35 ( Marks: 5 ) Consider the language L which is EVEN-EVEN, defined over Σ = {a,b}. In how many classes does L may partition Σ*. Explain briefly. Question No: 36 ( Marks: 5 ) What are the conditions (any five) that must be met to know that PDA is in conversion form? Virtual University of Pakistan - Network of Virtual University of Pakistan Students! Ans: Conversion form of PDA: A PDA is in conversion form if it has following conditions: 1. The PDA must begin with the sequence 2. There is only one ACCEPT state. 3. Every edge leading out of any READ or HERE state goes directly into a POP state. 4. There are no REJECT states. 5. All branching, deterministic or nondeterministic occurs at READ or HERE states. 6. The STACK is never popped beneath this $ symbol. 7. No two POPs exist in a row on the same path without a READ or HERE. 8. Right before entering ACCEPT this symbol is popped out and left. Question : Define Myhill Nerode Theorem. Question: How you Differentiate between wanted and unwanted branches while deriving a string from CFG? Question: What is the difference between concatenation and intersection of two FAs and Union and addition of two FAs? Question: Use Pumping Lemma II to show that following language is not regular L ={an2; n=1,2,3,4,…….} Question: Draw Moore Machine equivalent to the Following Mealy Machine? Question#1 Consider the CFG ( 5marks) S--> bS | aX | ^ X--> aX | bY | ^ Y--> aX | ^ Derive the following string from CFG. Show all steps baabab , ababaab Question#2 Construct corresponding CFG for the given language (5 mark) (1) All words of even length but not multiple of 3. (2) Palindrome (both even and odd palindrome). Question#3 Write the CFG for the following RE (a+b)* aa (a+b)* ( 5Marks) Question-4.What does the following arbitary summary table shows (3 Marks) From Where To Where READ What POP What Push What ROW number READ 9 READ3 b b abb 11 Question #5.Is the following CFG ambiguous? How can you remove the ambiguity? S→aS│bS│aaS│ ^ ( 3marks) Question# 6. If L1, L2, L3 are any three finite languages on , when will be the (3marks) Question#7.Construct RE for the language having words of even length over ∑= {a.b} (2 Mark) Question#8.A Push down Automata consists of and input TAPE with ----------many location in one direction. (Marks 2) Question# 9. Write alternative form of this production (2 Marks) Question 10. What is the first step when you want to write RE corresponding to TG (2Marks??) Question: 31 (Marks 1) Can you say that string of 0’s whose length is a perfect square is not regular? Question: 32 (Marks 1) Question: 33 (Marks 2) Is the following an FA or TM? Question: 34 (Marks 2) If L is the language that accept even length strings then what strings will Lc accept? Question: 35 (Marks 3) Define Myhill Nerode theorem Question: 36 (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: 37 (Marks 3) How you differentiate between wanted and unwanted branches while deriving a string from in the context of CFG? Question: 38 (Marks 5) What is the difference between concatenation and intersection of two FAs and union and addition of two FAs? Question: 39 (Marks 5) Use pumping lemma II to show that following language is not regular. L = {an2 ; n =1,2,3,4…} Question: 40 (Marks 10) Draw Moore Machine equivalent to the following Mealy Machine. Question: 41 (Marks 10) Write CFG of the following PDA. Also write the stack alphabet and tape alphabet. Question: 1 Use pumping lemma II to show that following language is not regular. L = {an2 ; n =1,2,3,4…} Question: 2 What is the difference between concatenation and intersection of two FAs and union and addition of two FAs? Question: 3 How you differentiate between wanted and unwanted branches while deriving a string from in the context of CFG? Question: 4 Can you say that string of 0’s whose length is a perfect square is not regular? 
|
|
Linear Mode
