FLAT Assignment-1 PDF [PDF]

Citation preview

Formal Languages and Automata Theory (CC1502) Assignment-1 (Due: Sep 02, 2019)



1. For Σ= {a, b}, construct DFA's that accept the sets consisting of a. all strings with exactly one a, b. all strings with at least one a, c. all strings with no more than three a's, d. all strings with at least one a and exactly two b’s, e. all the strings with exactly two a’s and more than two b’s. 2. With Σ = {a, b}, give a DFA for L= {w1aw2: |w1|≥ 3, |w2|≤ 5}. 3. Give DFA's for the languages a. L= {ab5wb2: w ∈ {a,b}*} b. L= {abnam: n ≥ 2, m ≥3} c. L= {w1abw2: w1 ∈ {a,b}*,w2 ∈ {a,b}*} d. L= {ban: n ≥ 1, n≠ 5} 4. Find DFA's for the following languages on Σ = {a,b} a. L= {w: |w| mod 3 = 0} b. L= {w: |w| mod 5 ≠ 0} c. L= {w: na(w) mod 3 > 1} d. L= {w: na(w) mod 3 >nb(w)mod 3} e. L= {w :(na(w) – nb(w)) mod 3 > 0} f. L= {w :(na(w)+2nb(w)) mod 3 < 2} g. L= {w: |w| mod 3 = 0, |w| ≠6} 5. Construct a DFA that accepts strings on {0,1} if and only if the value of the string, interpreted as a binary representation of an integer, is zero modulo five. For example, 0101 and 1111, representing the integers 5 and 15, respectively, are to be accepted. 6. Draw a FA recognizing the language by the regular expression (11+10)*01 7. Give the regular expression for string over {0,1}, whose length is multiple of 3. 8. Construct a DFA equivalent to the NFA shown below:



9. Construct a minimum state automaton equivalent to a given automaton M whose transition table is given in the following table States



Input a q0



b q3



q1



q2



q5



q2



q3



q4



q3



q0



q5



q4



q0



q6



q5



q1



q4



q1



q3



→ q0



10. Construct a Moore machine equivalent to the Mealy machine given below: Present State



Next State a=0



→



a=1



q1



State q1



Output State 1 q2



Output 0



q2



q4



1



q4



1



q3



q2



1



q3



1



q4



q3



0



q1



1