UNIT 1

1. Give DFA’s for each of the following languages over Σ = {a, b}: (a) All strings which do not contain the substring babb. (By a substring we mean a contiguous sequence of letters: thus u is a substring of w if there exist strings v1 and v2 such that w = v1uv2.) (b) Between every pair of b’s there is at least one a. (c) Strings which contain both aa and bb as substrings. (d) which contain an occurrence of aba or baa as a substring. 2. Give a DFA/NFA for all strings in {0, 1}∗ which represent (in binary) numbers which leave a remainder of 1 on dividing by 3. 3. Consider the NFA below: (a) Use the subset construction to obtain an equivalent DFA for the NFA below. Label each state of the DFA with the subset of states of the NFA that it corresponds to. (b) Give an 8 state DFA which accepts the same language