Theory of Automata BSCS 5th Term Past Paper 2017 UOS
University of Sargodha
BS 5th Term Examination 2017
Subject: Computer Science
Paper: Theory of Automata & Formal Languages (CS: 3131)
Time Allowed: 2:30 Hours
Maximum Marks: 80
Objective Part (Compulsory)
Q.No.1. Write short answers for the following questions. (16×2=32)
- What is the difference between the strings and the words of a language?
- What is the difference between an Alphabet and an element of a set. Whether Alphabet is an element of a set or it is a set itself?
- What is Null String (Λ)?
- What is PALINDROME?
- What is the concept of valid and invalid alphabets?
- What is ALGOL?
- What are the Sequential Operators?
- What is Non-Determinism and Determinism and what is the difference between them?
- What is meant by equivalent FA’s?
- Define Kleene Star?
- Differentiate Kleene Star Closure and PLUS?
- Define Regular Expression?
- What is the concept of the Union of FA’s?
- What is the corresponding FA for RE = aa((a+b)(a+b))*
- Differentiate between (a,b) and (a+b)?
- How diagrams of FA’s are created?
Subjective Part
Note: Attempt any three questions. (3×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
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. Determine the CFG, corresponding to the following FA:
(Diagram shown with states S, A, B, C+, and D+)
Q.No.5. Find the Context Free Grammar’s (CFG’s) for the following languages over the Σ = {a, b}.
i. All the words that do not contain substring abb.
ii. All the words that have exactly two or three b’s.
Q.No.6. Given a state diagram of FA as follows:
(Diagram shows states q1, q2, q3 with transitions labeled 0 and 1)
- Is 000111 accepted, is 10110?
- What set of strings accepts by the FA?
- What is the language recognized by the FA?