• Author / Uploaded
• Aiman Hafeez

Citation preview

Theory of Automata and Formal Languages Assignment-1 March 12, 2019

Submission Date: 18-03-2019 Problem-1 Write down the regular expressions for the following. The set of input alphabets in each case is Σ = {a, b} 1. All words in which a appears tripled. 2. All words that contain exactly two b’s or exactly three b’s, not more. 3. All strings that have exactly one double letter in them. 4. All strings in which the letter b is never tripled. This means that no word contains the substring bbb. 5. All words in which a is tripled or b tripled, but not both. 6. All words that do not have the substring ab. 7. All words that do not have substring bbb. 8. All strings in which the total number of a’s is divisible by 3 no matter how they are distributed, such as aabaabbaba.

Problem-2 Write regular expressions to describe each of the following languages: 1. { ω ϵ {a, b}* : every a in ω is immediately preceded and followed by b} 2. {ω ϵ {a, b}* : ω does not end in ba} 3. {ω ϵ {0, 1}* : x ϵ {0, 1}* (|x| is even)} 4. {ω ϵ {0, 1}* : ω has 001 as substring}

5. {ω ϵ {0, 1}* : ω does not have 001 as substring} 6. {ω ϵ {a, b}* : ω has bba as substring} 7. {ω ϵ {a, b}* : ω has both aa and bb as substrings} 8. {ω ϵ {a, b}* : ω has both aa and aba as substrings} 9. {ω ϵ {a, b}* : ω contains at least two b’s that are not followed by an a}

Problem-3 Let = {a, b, c}. 1. Give a regular expression for the set of all elements of Σ* containing exactly two b’s 2. Give a regular expression for the set of all elements of Σ* containing exactly two b’s and two c’s 3. Give a regular expression for the set of all elements of Σ* containing two or more b’s 4. Give a regular expression for the set of all elements of Σ* beginning and ending with a and containing at least one b and one c. 5. Give a regular expression for the set of all elements of Σ* consisting of one or more a’s, followed by one or more b’s and then one or more c’s.

Problem-4 Write down the regular expressions and draw DFSA also give the transition table for the following languages. The set of input alphabets in each case is Σ = {a,b}

1. L = {ω ϵ Σ* | ω contains even number of a’s}. 2. L = {ω ϵ Σ* | ω contains odd number of a’s}. 3. L = {ω ϵ Σ* | ω contains even number of a’s and odd numbers of b’s}. 4. L = {ω ϵ Σ* | |ω| is even}.

Problem-5 Find regular expressions that correspond to the following regular sets: 1. {ab, ac, ad} 2. {ab, ac, bb, bc} 3. {a, ab, abb, abbb, abbbb……} 4. {ab, abab, ababab, abababab, ababababab…….} 5. {ab, abb, aab, aabb} 6. {ab, acb, adb} 7. {ab, abb, abbb, abbbb……} 8. {ad, ae, af, bd, be, bf, cd, ce, cf} 9. {abcd, abcbcd, abcbcbcd, abcbcbcbcd,……..} 10. {abcd, abef, cdcd, cdef}