NAME HERE Assignment 6 Discrete Math H12
Problem 1
Either write a regular expression for, or construct an FSA/NFA for, the following languages. In each
case, the alphabet is indicated.
A Strings that contain at least two a’s and at most one b. Σ = {a, b}
B Strings where every odd position is an a. Σ = {a, b, c}
C Strings that do not contain the substring abba. Σ = {a, b, c}
Proof:
Problem 2
Describe in English the languages accepted by the following regular expressions. In each case,
construct an NFA that will accept the described language by breaking down the regular expression. You
may assume the alphabet in each case only contains the symbols mentioned in the regular expression.
Use the rules for constructing NFAs from regular expressions that we went over in class to construct
these.
A aa∗ b
B ((a ∪ b)∗ c) ∪ d∗
Proof:
Problem 3
For the following question, refer to the NFA called M below:
Convert this NFA into a GNFA and generate a regular expression accepting the same language, using
the algorithm from class. Do not use any abbreviations/simplifications for the final regular expression.
Proof:
Problem 4
Let Bn = {ak | k is a multiple of n}. Show that for any n ≥ 1, Bn is a regular language.
Proof:
1
NAME HERE Assignment 6 Discrete Math H12
Problem 5*
Suppose we have a language A with alphabet Σ. We can define the insertion operation on a word
w ∈ Σ∗ and A to produce the set of all possible strings obtained by inserting w in the middle of a string
from A. Formally, we can define insert using ← notation as:
A ← w = {xwy| xy ∈ A}
A Show that for any regular language A and any word w on the same alphabet, A ← w is also
regular.
B We can define insert on two languages instead of a language and a word. Given two languages A
and B, takes A ← B to be A ← w for every possible w ∈ B. More formally:
[
A←B= A←w
w∈B
Show that the regular languages are closed under insert.
Proof:
Problem 6
Take language C to be:
C = {ai bj ck |i, j, k ≥ 0, and if i = 1, then j = k}
Show that C is not regular.
Proof:
Problem 7
Take language A to be:
A = {am bn | m ̸= n}
Show that A is not regular. (Hint: This proof can be done with the pumping lemma but it is easier
to do it without the pumping lemma! Recall that there are many operations under which the regular
languages are closed – this means that if you apply one of those operations to A, and the resulting
language is not regular, than neither is this one.)
Proof:
