NATIONAL OPEN UNIVERSITY OF NIGERIA

UNIVERSITY VILLAGE, PLOT 91, CASDASTRAL ZONE, NNAMDI AZIKIWE EXPRESS WAY, JABI, ABUJA.
FACULTY OF SCIENCES
SEPTEMBER 2020 EXAMINATION

COURSE TITLE: Formal Languages and Automata Theory

COURSE CODE: CIT342

CREDIT UNITS: 3

TIME ALLOWED: 2½ Hours

INSTRUCTION: Answer Question 1 and any other FOUR (4).

QUESTION ONE

a. The following are the state diagrams of two DFAs M1 and M2. Answer the following questions about each of the machines.

i. Give the formal description of the Machines M1 and M2. (3 marks )

ii.What are the start states of M1 and M2? (1 mark)

iii.What are the set of accept states for M1 and M2? (1 mark)

iv.What sequence of states does machine M1 and M2 go through on input aabb? (1 mark)

vii.Does the machine accept the string aabb? (1 mark)

vii.Does the machine accept the strings Є? (1 mark)

b.) Show that the collection of decidable languages is closed under the operation of union. (4 marks)

c) Construct the context-free grammar that generates the following language. {w|the length of w is odd and its middle symbol is a 0} (2marks)

e) Give implementation-level description of Turing machine that decide the following languages over the alphabet {0, 1} {w|w contains an equal number of 0s and 1s} (8 marks)

QUESTION TWO

a. Explain the Chomsky normal form. (2marks)

b. Let G be a context-free grammar with productions

S → TU|V

T → aTb|λ

U → cU|λ

W → bW|λ

i. Identify nullable variables in the grammar ( 1 mark)

ii. Eliminate the λ-production. (3 marks)

iii. Identify A-derivable variables for each A (1 mark)

iv. Eliminate unit productions. (1 mark)

v. Converting to Chomsky normal form (4 marks)

T1 - T2

Each transition of an FST is labeled with two symbols, one designating the input symbol and the other designating the output symbol. The two symbols are written with a slash, / , separating them. In T1, the transition from q1 to q2 has the input 2 and output symbol 1. Some transitions may have multiple inputoutput pairs, such as the transition in T1 from q1 to itself. When an FST computes on an input string w, it takes the input symbols w1...wn one by one and, starting at the start state, follows the transition by matching the input labels with the sequence of symbols w1...wn = w. Every time it goes along a transition, it outputs the corresponding output symbol. For example, on input 2212011, machine T1 enters the sequence of states q1, q2, q2, q2, q2, q1, q1,q1 and produces the output 1111000. On input abbb, T2 outputs 1011. Give the sequence of states entered and the output produced in each of the following parts.

T1 on input 011 (1 mark)

T1 on input 211 (1 mark)

T1 on input 121 ( 1 mark)

T1 on input 0202 ( 1 mark)

T2 on input b (1 mark)

T2 on input bbab ( 1 mark)

T2 on input bbbbbb ( 1mark)

b. Use the pumping lemma to show that the language L = { a2n | n ≥ 0} (5 marks)

QUESTION FOUR

Create a Pushdown Automaton (PDA) for recognizing the language {wwR | w Є { 0,1 }* } (12 Marks)

QUESTION FIVE

Construct an NFA and DFA for the language over the alphabet ∑ = {a,b} that contains all strings that have abb as substring. (12 Marks)

QUESTION SIX

a.Prove that the language E = {0i 1 j | i > j } is not regular. (6 marks)

b. Give the state-set implementation of NFAs. (6 marks)