Theory of Automata BSCS 5th Term Past Paper 2015 UOS

University of Sargodha
BS(CS), 5th Term Exam 2015
Paper: Theory of Automata & Formal Languages (CS:211)
Time Allowed: 2:30 Hrs
Max. Marks: 80

Objective Part (Compulsory)

(16 x 2 = 32)

Q.No.1. Write short answers for the following questions.

1. What is the Principle of Mathematical Induction?
2. Define Regular Languages?
3. What is a Regular Expression? Shortly discuss it with an example?
4. What is a Finite Automata? Shortly discuss it with an example?
5. Which language, this regular expression {00+01+10+11}* presents?
6. Define NFA with an example?
7. Give an example of an NFA accepting {0}{1}*
8. Define Λ-Closure of a set of states regarding NFA.
9. Define Non-regular languages?
10. What does PDA mean? Provide an example?
11. Define Context Free Grammars?
12. Define Chomsky’s Normal form?
13. Discuss Turing Machines shortly with an example?
14. What is Minimal Finite Automata?
15. What is Universal Turing Machines?
16. What does Context Sensitive Grammar mean?

Subjective Part

Note: Attempt any 03 questions. (3 x 16 = 48)

Q.No.2. Provide regular expressions of the following, where Σ = {0, 1}:
i. Strings of length six or less
ii. Strings with Next-to-Last symbol is 0
iii. Strings ending with 0
iv. Strings with even number of 0’s and odd number of 1’s

Q.No.3. If L₁ = {a, ab} and L₂ = {ab} then find the Union, Intersection and Complement between L₁ and L₂. Also draw their respective automata and explain each step properly.

Q.No.4. Design Finite Automaton for the following regular expressions or languages:
i. {00}{11}
ii. {11+110}0
iii. {0,1}{10}
iv. Strings containing either ab or bba

Q.No.5. Convert the following NFA to DFA using Subset Construction Method, where Q4 is the accepting state.

(A diagram of NFA with states Q1, Q2, Q3, Q4 and transitions is shown here)

Q.No.6. Prove that the language L = 1ⁿ2ⁿ is a non-regular language, where n ≥ 0.