Theory of Automata BSCS 5th Term Past Paper UOS
DEPARTMENT OF COMPUTER SCIENCE Q#1
UNIVERSITY OF SARGODHA
Subject: Theory of Automata
Time: 2 hrs.
Final TERM
CLASS: BSCS 5th (Reg + Self)
Marks: 50
Roll no: 22
Q.1
Give brief explanation
[2 * 5]
a) When a CFG is said to be in GNF?
b) Why Context Free Grammars called “Context Free”?
c) What are the Productions?
d) How Moore and Mealy machine works in Computer memory what is their importance in computing?
e) What is the difference between Parse tree and Total Language tree?
Q.2
[5 + 5]
a) Convert the Following CFG to CNF
- S → Aad
- A → aB / bAB
- B → b
- D → d
b) What is ambiguous Grammar? Prove that following CFG is ambiguous.
- S → XbaX / aX
- X → Xa / Xb / λ
Q.3
[2.5 * 4]
a) Using Pumping Lemma show that { a^n3 | n is a non-negative number } is non regular language.
b) Write CFG for the language over the alphabet {0,1} that have the set of all strings whose 10th symbol from the right end is ‘1’.
c) Write CFG for the language over the alphabet {a,b} that accept all string having ‘a’ at every odd position.
d) Write CFG for the language over the alphabet {a, b} accept all words that start with a (followed by odd a’s and odd b’s).
Q.4
[6 + 4]
a) Design a PDA for the following language
- a^m b^n a^m where m ≥ n and m, n ≥ 0
b) Design a PDA for the language that accepts all words that do not ends on double Letter.