Theory of Automata MSc IT 3rd Term Past Paper 2014 UOS

University of Sargodha

M. Sc. I. T., 3rd Term Exam 2014.

Subject: Information Technology
Paper: Theory of Automata & Formal Languages (IT: 694)
Time Allowed: 2:30 Hour
Session: 2012-14
Maximum Marks: 80

Objective Part

Q.1. Write short answers of the following in 2-3 lines each on your answer sheet. (2*16)

(i) Explain the difference between the transition functions of DFA and NFA.
(ii) Construct a nondeterministic automata accepting the set of all strings over (a, b) ending in ab.
(iii) What is Equal RE?
(iv) What are the basic rules to build FA?
(v) Write down the importance of Moore and Mealy machine in computing?
(vi) What is the difference between Palindrome and Reverse function?
(vii) Differentiate Kleene Star Closure and PLUS?
(viii) What is the corresponding FA for RE = aa((a+b)(a+b))*
(ix) Why we need TG’s when we have FA’s?
(x) What is the concept of the Union of FA’s?
(xi) Differentiate between (a,b) and (a+b)?
(xii) What are the Productions?
(xiii) What is the uses of push down automata in computing?
(xiv) What is difference between PUSH DOWN STACK and PUSH DOWN STORE?
(xv) What is meant by the terms stack consistence and input tape consistence?
(xvi) What is Left most Derivation in CFG?

Subjective Part (4*12)

Q.2.
a) List down the types of Automata and how these types differ from each other?
b) What is the difference between Nullable and Null production? How to make eliminate Nullable and for Null Productions from the CFG?

Q.3. Build a Finite Automata (FA) that accepts only those words that [43=12]
i. Either have an odd number of letters or end in a
ii. Odd number of b
iii. Have even a’s and even b’s
iv. (a+b)(aa+bb)(a+b)*

Q.4. Build a Turing Machine that accepts the following language [6*2=12]
a) {aⁿbⁿ⁺¹}
b) {aⁿb²ⁿ}