Theory of Automata and Formal Languages BE UOS — University of Sargodha 2016

DEFARTVIENI OF COMPOTEN OCE

UNIVERSTY OF SARGODHA

Time: 2 hrs.

Marks: 50

Subject: Theory of Automata

Roll no-

Q.1

Final TERM

Give brief explanation

a) When a CFG is said to be in GNF?

ustani.pk

b) Why Context Free Grammars called "Context Free"?

ustani.pk /2*/

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?

［5+5］

a) Convert the Following CFG to CNF

SI

Aad

aB / bAB

B

D

b) What is ambiguous Grammar? Prove that following CFG is ambiguous.

XbaX / aX

Ха / Хь / Л

‚4

［2.54］

Using Pumping Lemma show that { a" [n is a non-negative number }is non regular

We rie CFG for the language over the alplabet (0.1) that have the set of all strings whose

10" symbol from the right end is 20-

White CrO for the language guer the alplabet (n.b) that accept all string having *a' at

every odd position.

Write CFG for the language over the alphabet fa.

b) accept all alds that start with a

(followed by odd a's and odd b's)

［6+4］

Design a PDA for the following language

a"b"amn where min and m.n.≥0

Design a PDA for the language that accept: all words that do not ends on double Letter.

visit website: ustani.pk