CSC420 Computing Theory

HW \# 1: Consider the following DFA over ={a,b} : - DFAI recognizes language LI=L(MI). DFA1 M1 for L. a) Construct a DFA for the language L1*. b) What is the regular expression (RE) for L.1? a) Consider the following NFA- over ={a,b} : Convert this NFA-E into DFA. Answer: b) Build NFA for L((ba)(ab)) over ={a,b}. HW 3: a) Consider the following CFG : SaSaXa 1) What is the regular expression (RE) accepted by this CFG? 2) Show that whether this CFG is ambiguous or not: 3) Show that whether the word "abaaa" is accepted or not by this CFG: b) Considering the below PDA, give the (state; stack) evolution of input string w=abb. HW 4: Convert the following CFG into an equivalent CFG in Chomsky Normal Form(CNF) over the ={a,b}.SaSabXXbaYYaaX