CSCI 383: Theory of Computation Homework 5 Spring 2019 Due: March 11 and 13
Reading: Sections 19, 20, 21.
Questions: Select any one part to be handed in at the beginning of class on Monday. The remaining parts must be completed and handed in during class on Wednesday. Your solutions must be typeset in LaTeX. Figures may be drawn by hand. Each solution must be handed in separately. Print front and back. If a single solution requires multiple pages, staple them. List your collaborators and include the honor code.
Part 1: Mboarbeb Cblaobsbuarbeb
Given a language A over the alphabet Σ, we can define a new language
Expand(A) = {x = a1b1a2b2 …anbn | y = a1a2 …an ∈ A and bi ∈ Σ}.
That is, Expand(A) is the set of strings generated by taking a string x from A and adding an extra, arbitrary character after every character in x. For example,
Expand({aa, bb}) = {aaaa, aaab, abaa, abab, baba, babb, bbba, bbbb}.
Using regular expressions, prove that the set of regular languages is closed under the Expand operation. In other words, given a regular expression α, show how to construct a regular expression α′ such that L(α′) = Expand(L(α)), and prove that this is the case.
Part 2: Building Expressions
Give regular expressions for each of the following languages. Simplify as much as you can. Exces- sively complicated expressions might not get full points. No proofs required, but if explaining your regular expression might help the reader see what’s going on, feel free.
1. All strings x over {a, b} with an even number of a’s.
(There’s an expression with 11 characters, including (, ), ∗, and +.)
2. All strings x over {a, b} with #a(x) ≡ #b(x)(mod 2).
(There’s an expression with 13 characters, including (, ), ∗, and +.)
3. All strings over {a, b} that do not contain the (contiguous) substring aba. (There’s an expression with 13 characters, including (, ), ∗, and +.)
Part 3: Regex Against the Machines
Draw NFAs for the following languages. No need to prove your NFAs are correct, but you should explain how you got to your answer. Your life might be improved by trying to simplify the regular expression somewhat first.
1
1. (0 + 1)∗000(0 + 1)∗
2. (((00)∗(11)) + 01)∗
3. (ab+ε)(b+ε)∗
2