CS402 Final term Subjective Papers 1

CS402 Theory of Automata Finalterm Subjective Papers

Finalterm Paper 2011 

Total questions = 52
2 marks questions

•  What is Transition?
•  Alternative form of this production        S=>aS, S=> bS, S=> A(Null).
•  What is input Tap?
•  What is live production?

3 marks questions

•  Differentiate between Distinguishable and Indistinguishable strings.
•  What is wanted and unwanted branches.
•  Table given of arbitrary summary.
•  Find Pref(Q in R).

5 marks questions:

•  What is unit of production.
•  What do u know about NFS?
•  Define two rules ………………(Row Language.).
•  (L1UL2^C) intersection (L1^CU L2) the language or accept any thing or not?

 Final Paper 2010

1. What is Row Language?
2. What does FA stands for?
3. What are living and dead productions?
4. Given a summary table, we were required to explain it.
5. What do you mean by wanted and unwanted branches?
6. Given an FA, I had to recognize the language - EVEN-EVEN
7. Given the CFG, had to write the language (EQUAL)
8. Construct corresponding CFG for the given language.
(1) All words of even length but not multiple of 3.
(2) Palindrome (both even and odd palindrome). (5 mark)
9. Who invented Turing m/c?
10. Equivalent /non-equivalent languages.
11. What are formal languages?

      

 Finalterm Paper 2009

Time 2 Hours
Total questions 41
Objective questions 31
Subjective question 10

 Question: 31                                        (Marks 1)

Can you say that string of 0’s whose length is a perfect square is not regular?

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.

Cs402 Final term Subjective papers

CS402 - Theory of Automata - Short Questions 

Question No: 27    ( M a r k s: 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  ( M a r k s: 2 )

What is meant by a "Transition" in FA?

Question No: 29    ( M a r k s: 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    ( M a r k s: 2 )

Identify the null productions and nullable productions from the following CFG:

S -> ABAB

A -> a | /\

B-> b | /\

Question No: 31    ( M a r k s: 3 )

Describe the POP operation and draw symbol for POP state in context of Push down stack.

Question No: 32    ( M a r k s: 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    ( M a r k s: 3 )

Find Pref (Q in R) for:

Q = {10, 11, 00, 010}

R = {01001, 10010, 0110, 10101, 01100, 001010}

Question No: 34    ( M a r k s: 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    ( M a r k s: 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    ( M a r k s: 5 )

What are the conditions (any five) that must be met to know that PDA is in conversion form?

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 ={an²;  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 = {an² ; 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?

CS402 Final term Paper 2010

FINALTERM  EXAMINATION

Spring 2010

CS402- Theory of Automata (Session - 1)

Time: 90 min

M a r k s: 58

CS402 Question No: 1       

If r1 = (aa + bb) and r2 = ( a + b) then the language (aa + bb)(a + b) will be generated by 

► (r1)(r2) 

*► (r1 + r2) 

► (r2)(r1) 

► (r1)* 

CS402 Question No: 2         

 “One language can be expressed by more than one FA”. This statement is ______ 

* ► True 

► False 

► Some times true & sometimes false 

► None of these 

CS402 Question No: 3         

 Who did not invent the Turing machine?  

► Alan Turing 

*► A. M. Turing 

► Turing 

► None of these 

CS402 Question No: 4         

 Which statement is true? 

*► The tape of turing machine is infinite. 

► The tape of turing machine is finite. 

► The tape of turing machine is infinite when the language is regular 

► The tape of turing machine is finite when the language is nonregular. 

CS402 Question No: 5         

 A regular language: 

*► Must be finite 

► Must be infinite 

► Can be finite or infinite 

► Must be finite and cannot be infinite 

CS402 Question No: 6         

 Every regular expression can be expressed as CFG but every CFG cannot be expressed as a regular expression. This statement is: 

► Depends on the language 

► None of the given options 

*► True 

► False 

CS402 Question No: 7         

   

Above given FA corresponds RE r. then FA corresponding to r* will be 

  

This statement is  

*► True 

► False

► Depends on language

► None of these

CS402 Question No: 8       

Consider the language L of strings, defined over Σ = {a,b}, ending in a

►There are finite many classes generated by L, so L is regular

*►There are infinite many classes generated by L, so L is regular

►There are finite many classes generated by L, so L is non-regular

►There are infinite many classes generated by L, so L is non-regular

CS402 Question No: 9       

Above given TG has _____________ RE.

► (aa+aa+(ab+ab)(aa+ab)*(ab+ba))*

*► (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*

► (aa+bb+(ab+ba)(aa+bb)(ab+ba))*

► None of these

CS402 Question No: 10       

The word ‘formal’ in formal languages means

*► The symbols used have well defined meaning

► They are unnecessary, in reality

► Only the form of the string of symbols is significant

► None of these

CS402 Question No: 11       

Let A = {0, 1}. The number of possible strings of length ‘n’ that can be formed by the elements of the set A is

► n!

*►  n²

► n^m

► 2ⁿ

CS402 Question No: 12       

Choose the correct statement.

► A Mealy machine generates no language as such

► A Moore machine generates no language as such

*► A Mealy machine has no terminal state

► All of these

CS402 Question No: 13       

TM is more powerful than FSM because

► The tape movement is confined to one direction

*► It has no finite state control

► It has the capability to remember arbitrary long sequences of input symbols

► None of these

CS402 Question No: 14       

If L1 and L2 are expressed by regular expressions r1 and  r2, respectively then the language expressed by  r1 + r2 will be _________

* ► Regular

► Ir-regular

► Can’t be decided

► Another Language which is not listed here

CS402 Question No: 15       

Like TG, a PDA can also be non-deterministic

► True

*► False

CS402 Question No: 16       

The above machine is a/anTG ___________

► Finite Automata

*► Turing machine

► FA

► TG

CS402 Question No: 17       

The language of all words (made up of a’s and b’s) with at least two a’s can not be described by the regular expression.

► a(a+b)*a(a+b)*(a+b)*ab*

► (a+b)* ab* a(a+b)*

► b*ab* a(a+b)*

► none of these

CS402 Question No: 18       

In FA, if one enters in a specific state but there is no way to leave it, then that specific state is called

*► Dead State

► Waste Basket

► Davey John Locker

► All of these

CS402 Question No: 19       

If L is a regular language then, L^c is also a _____ language.

*► Regular

► Non-regular

► Regular but finite

► None of the given

CS402 Question No: 20       

In CFG, the symbols that can’t be replaced by anything are called___

► Terminal

► Non-Terminal

*► Production

► All of given

CS402 Question No: 21       

Which of the following is NOT a regular language?

► String of 0’s whose length is a perfect squere

*► Set of all palindromes made up of 0’s and 1’s

► String of 0’s whose length is a prime number

► All of the given options

CS402 Question No: 22       

Choose the incorrect (FALSE)  statement.

► A Mealy machine generates no language as such

► A Mealy machine has no terminal state

*► For a given input string, length of the output string generated by a Moore machine is not more than the length of the output string generated by that of a Mealy machine

► All of these

CS402 Question No: 23       

Pumping lemma is generally used to prove that:

► A given language is infinite

*► A given language is not regular

► Whether two given regular expressions of a regular language are equivalent or not

► None of these

CS402 Question No: 24       

Which of the following is a regular language?

► String of odd number of zeroes

► Set of all palindromes made up of 0’s and 1’s

*► String of 0’s whose length is a prime number

► All of these

CS402 Question No: 25       

Choose the incorrect statement:

► (a+b)*aa(a+b)* generates Regular language.

► A language consisting of all strings over ∑={a,b} having equal number of a’s and b’s  is a regular language

► Every language that can be expressed by  FA can also be expressed by RE

► None of these

CS402 Question No: 26       

Left hand side of a production in CFG consists of:

► One terminal

► More than one terminal

► One non-terminal

* ► Terminals and non-terminals

CS402 Question No: 27    ( M a r k s: 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.

CS402 Question No: 28    ( M a r k s: 2 )

What is meant by a "Transition" in FA?

CS402 Question No: 29    ( M a r k s: 2 )

What are the halt states of PDAs?

Ans:

There are some halts states in PDA which are as:

1. Accept or reject stat is also halt state.
2. Reject state is like dead non final state.
3. Accept state is like final state.

CS402 Question No: 30    ( M a r k s: 2 )

Identify the null productions and nullable productions from the following CFG:

S -> ABAB

A -> a | /\

B-> b | /\

CS402 Question No: 31    ( M a r k s: 3 )

Describe the POP operation and draw symbol for POP state in context of Push down stack.

CS402 Question No: 32    ( M a r k s: 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 someother 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.

CS402 Question No: 33    ( M a r k s: 3 )

Find Pref (Q in R) for:

Q = {10, 11, 00, 010}

R = {01001, 10010, 0110, 10101, 01100, 001010}

CS402 Question No: 34    ( M a r k s: 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

CS402 Question No: 35    ( M a r k s: 5 )

Consider the language L which is EVEN-EVEN, defined over Σ = {a,b}. In how many classes does L may partition Σ*. Explain briefly.

CS402 Question No: 36    ( M a r k s: 5 )

What are the conditions (any five) that must be met to know that PDA is in conversion form?

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 HEREstate 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.

CS402 Final term Subjective Papers

CS402 Papers shared by STUDENT

CS402- Current:

AoA

mera to auto ka pap 75% past paps mese tha (jo k khushqismati se pap ki subh hi kholne ki tofeeq ki gai thi) anyways pap mera acha ho gya,bht acha is lye nahi k baki 25% b to tha lolzzz

hehe

ya sure!

52 total Q the,120 mnts,40 mcq's ,4Q k 2 marks,or 4Q k 3marks or 4Q k 5marks.total marks 80.RE k 1 2 mcqs the  polish notation thi(o-o-o),

CNF ki definition,PDA in conversion form ki charactrestics thi

ambiguous grammer,

meally more me se 3 4 mcqs the,prefix ka 1 Q tha,

itna e yad...

Total Question 45

40(1) + 3(2 marks) + 3(3 marks) + 3(5 marks)

1. Difference between semi-word and word with example?
2. If there are more than one edges between two states then we can replace them by one edge in a TG. Explain it with examples?
3. How can you say that two FAs are equivalent?

Note: There were three questions related to equivalent of FAs and/ or Languages?

4. A graph was given and infix and prefix calculation of that graph was required like

Note: Here only 5 was replaced by 7.

5. What is a production?
6. This example was same in the Paper. Is it ambiguous? How can we eliminate Ambiguity?

Assalamoalaikum.........

today's automata paper was really confusing........false n true statement bohat hi chicher qisam ki theen.....

moor n mealy machine say thay mcq.....TM say related thay.......mid say related stuff say bhi kafi aaya tha.......

40 mcq thay

2marks k i think 3 n

3 k bhi 3 and

5 k bhi 3 thay.......

even n odd palendrome k CFG thay ....even language ka CFG without multiple of 3 aaya tha.....5 marks

pop n push .......both n separately ...2 and 3 marks..

differentiate Live Production, Dead Production 5 marks .....

ak important q meray pass tha last papers ka yeah bhi aaya tha......

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) ≠ Ø

CS402 Mid term MCQs Solved

 CS402-Midterm-Paper-Theory-of-Automata

Attachments:

CS402-Midterm-Paper-Theory-of-Automata-mcqs

[]

318 Kb