Foundations Regular Expressions and Regular Languages

HW03-01 – Foundations
Regular Expressions and Regular Languages
Reminder: Just because a problem is optional doesn’t mean that you don’t need to know how
to do it, it’s just my attempt to give you a little less written work!
Problem 1
Find a language (i.e., a set of strings) to describe each of the following regular expressions.
a. a + b.
b. a + bc.
c. a + b*.
d. ab* + c.
e. ab* + bc*.
[optional] f. a*bc* + ac.
Problem 2:
Find a regular expression to describe each of the following languages.
a. {a, b, c}.
b. {aa, ab, ac}.
c. {a, b, ab, ba, abb, baa, … , abn, ban, . . . }.
d. {a, aaa, aaaaa, … , a2n+1, . . . }.
e. {Λ, a, abb, abbbb, … , ab2n, . . . }.
f. {Λ, a, b, c, aa, bb, cc, … , an, bn, cn, . . . }.
g. {Λ, a, b, ca, bc, cca, bcc, … , cna, bcn, . . . }.
h. {a2k | k ∈ N} ∪ {b2k+1 | k ∈ N}.
i. {am bcn | m, n ∈ N}.
Problem 3
Find a regular expression over the alphabet {0, 1} to describe the set of all binary numerals without
leading zeros (except 0 itself). So the language is the set {0, 1, 10, 11, 100, 101, 110, 111, . . . }.
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 4:
Find a regular expression for each of the following languages over the alphabet {a, b}.
a. Strings with even length.
b. Strings whose length is a multiple of 3.
c. Strings containing the substring aba.
d. Strings with an odd number of a’s.
Problem 5
Use set notation to describe the language of all strings of length less than or equal to 3 over the alphabet {a,b}
Problem 6
Now describe the same language as a regular expression
Problem 7
Assume you have the following definitions for all the problems in this part:
A = {y,z}
B = {profs}
C = {a,e,i,o,u}
D = The set containing all the lowercase letters in the English alphabet
a) Let Q1 be the language that contains all strings of length two over the alphabet A
● Express Q1 as a set
● Is Q1 a regular language over the alphabet A? Explain how you know
b) Let Q2 = BC
● Express Q2 as a set
● Is Q2 a regular language over the alphabet D? Explain how you know
c) Let Q3 = B*
● Express Q3 as a set
● Is Q3 a regular language over the alphabet D? Explain how you know
[Optional] d) Let Q4 = the set of all strings of length 74 over the alphabet D
● Is Q4 a regular language over the alphabet D ? Explain how you know
[optional] e) Let Q5 = the set of all strings over the alphabet C that contain just e’s
● Is Q5 a regular language over the alphabet D? Explain how you know
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 8.
Find a language (i.e., a set of strings) to describe the following regular expression: bab + c
Problem 9
a. Find a language (i.e., a set of strings) to describe the following regular expression: ab*c*
b. [optional] explain why it represents the same language as the following other regular expressions:
○ a + ab*c*
○ abc + ab*c*
○ a + ab + ac + abc + abb + abc + acc + ab*c*
Problem 10
a. Find a language (i.e., a set of strings) to describe the following regular expression: (a+b)*(cd)
b. [optional] explain why it represents the same language as the following other regular expressions:
○ (a+b)*(cd)+ cd
○ acd + bcd + (a+b)*cd
Problem 11
a. Find a language (i.e., a set of strings) to describe the following regular expression: (a+b)(cd)*(a+b)
b. [optional] Then, explain why it represents the same language as the following other regular expressions:
○ acda + (a+b)(cd)*(a+b)
○ acdcdcdb + (a+b)(cd)*(a+b)
○ aa + ab + ba + bb + (a+b)(cd)*(a+b)
Problem 12
a. Find a language (i.e., a set of strings) to describe the following regular expression: (ab+bc)(aa)
b. [optional] Then, explain why it represents the same language as the following other regular expressions:
○ abaa + bcaa
○ (Λ)(ab)(aa) + (bc)(aa)
Problem 13
a. Find a language (i.e., a set of strings) to describe the following regular expression: (ab)*(c+d+e)(ab+bc)*
b. [optional]Then, explain why it represents the same language as the following other regular expressions:
○ c+d+e+cab+cbc+(ab)*(c+d+e)(ab+bc)*
○ (ab)*(c+d+e)(ab+bc)*+abcab + abdab + abeab
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 14
a. Find a language (i.e., a set of strings) to describe the following regular expression: (aa)*ab
b. [optional] explain why it represents the same language as:
○ ab + aaab + (aa)*ab
○ (aa)*ab + aaaaaaab
Problem 15
Find a regular expression to describe the following language: {b, aba, abba}
Problem 16
Find a regular expression to describe the following language: {rowan} ∪ {rules}
Problem 17
a. Find a regular expression to describe the following language:
{rowan} ∪ {is, awesome}
b. [optional] Then, explain why your regular expression also represents the following languages:
● {rowan, is, awesome}
● {rowan} ∪ {is} ∪ {awesome}
Problem 18
a. Find a regular expression to describe the following language: {Λ, a, ab, abb, abbb}
b. [optional] explain why your regular expression also represents the following languages:
● {Λ,a} ∪ {a}{b,bb,bbb}
● {Λ, a, ab} ∪ {ab}{b,bb,bb}
Problem 19.
a. Find a regular expression to describe the following language:
{Λ, a, aa, aaa, aaaa, aaaaa …}{Λ, b, bb, bbb, bbbb}
b. [optional] Then, explain why your regular expression also represents the following languages:
● {a}*{Λ, b, bb, bbb, bbbb}
● {Λ}{a}* ∪ {a}*{b, bb}{bb} ∪ {a}*{b,bb}
Problem 20
Find a regular expression to describe the following language:
{abna| n ∈ ℕ}
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 21
Let L&M be languages where
● L = {a, b, bb} and
● LM = { a, b, ab, bb, abb, bbb, bbbb}
What is M?
Problem 22
Find a regular expression to describe:
The set of all strings over the alphabet {a, b, c} that start with the substring bc
So, for example, the following strings are in the language:
● bc, bca, bcc, bcbc, bcbcbc, bcaaaaaa, bcbbbb, bccb
And the following strings are not in the language:
● bac, cbca, bbbccc, abc, aaabc, aababa
Problem 23
Find a regular expression to describe:
The set of all strings over the alphabet {a, b, c} that always contain the substring “bc” (at least one or
more times)
So, for example, the following strings are in this language:
○ bc, abc, aaaaaaaaabc, abcba, bc, bcb, aaaabcaaacbc, bbc, bcabc
and the following strings are NOT in this language:
cb, acb, aaaa, bbbb, c, b, a, bronco, cccccccccccccabac
○
Problem 24
Find a regular expression to describe:
The set of all strings over the alphabet {a, b, c, d} that contain exactly one a and exactly one b
So, for example, the following strings are in this language:
● ab, ba, cccbad, acbd, cabddddd, ddbdddacccc
and the following strings are NOT in this language:
● a, ccbc, acbcaaacba, acacac, bcbbbbbca, aca, c, d, b
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 25
Find a regular expression to describe L, where L = The set of strings over the alphabet {a, b, c, d} where every “c” is
immediately preceded and also followed by a “b” (i.e. every “c” has the symbol “b” right next to it on both sides) So,
for example … These strings are in L:
○ a, b, d, bcb, abbbbcbddabcb, abd, dbcbcb, bcbcb
and these strings are NOT in L:
○ abc, abcbabc, asdc, cbbb, acb
Problem 26
Find a regular expression to describe m, where M = the set of strings over the alphabet {a,b,c,d} which start with the
letter ‘a’ or the letter ‘b’ and also contain exactly one c
For example, the following strings are in M:
● ac, bc, abc, abcba, bcbd, bbbbbbc, aaaaaabbbbcdd, bbbbcaaa
and these are NOT in M:
● abcbabc, a, b, c, d, ca, dbbbacbba, bcabcd
Problem 27:
Find regular expressions for each of the following languages over the alphabet {a, b}
a. No string contains the substring aa.
b. No string contains the substring aaa.
c. No string contains the substring aaaa.
Problem 28:
Give a regular expression that describes the set of all strings over the alphabet {p,r,o,f} that:
Contain exactly two f’s
AND
DO NOT contain any p’s
So, for example, the following strings are in the language:
● ff, rfoof, ofofo, rffoo, froofroo, ffo, off, rororofrorrrrf, rorooorofrofooo, rrrrrrrrrrrrfrrrrrrrrrfrrr,
foooooooooof, ooooooff
And the following strings are not in the language:
● Λ, p, r, o, f, pff, fpfooo, oofoofof, roooro, froo, oorforopo, froofroop, fropofroo, oorforoo
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 29:
Give a regular expression that describes the set of all strings over the alphabet {p,r,o,f} that:
(Start with p AND end with f)
OR
(Contain the substring pff)
(Note: assume that AND and OR above have their meanings in logic. I added parenthesis around the
clauses so there is no ambiguity)
So, for example, the following strings are in the language:
● pf, pff, ppfff, prof, propffrof, oopffrr, rprorpffrrpffrooo, ppff, rprorffrrpffrooo,
pppppppppffppppppp, pffpffpffpff, opffpffpffo
And the following strings are not in the language:
● Λ, r, o, p, f, ff, rr, oro, poro, ppfppfofo, rropoorf, proforp, fppf, ffppfof, fppfpf, pfpfpfpfp, oopfrfrr
Problem 30
Find a regular expression to describe:
The set of all strings over the alphabet {a, b, c} that end with bcb
So, for example, the following strings are in the language:
● bcb, abcaabacbcb, abcacbabcb, abcccbcb, aaaaabcb, cbcbcb
And the following strings are not in the language:
● Λ, a, b, c, ab, cba, ccc, abbccaabc, cbabc, aabcacb, acca, bcbc
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 31
Find a regular expression to describe:
The set of all strings over the alphabet {a, b, c} where:
●
●
The string may or may not include b’s
If the string has at least one b then:
○ It must have an even number of b’s, and
○ Every b must be adjacent to at least one other b, and
○ Adjacent b’s must be in groups of even numbers
Hint: These rules mean that:
●
●
You never have an odd number of b’s next to each other
You can think of it as needing to have pairs of b’s next to each other
So, for example, the following strings are in this language:
●
Λ, bb, cbb, ccccbbbbcc, aa, bbbbccbbcc, abbbbbbacca, a, abb, bbabbccbbbba, ccca
And the following strings are NOT in this language:
●
ba, bab, bbb, abc, cbccccccaab, aaaababc, bababa, ababbccb
[optional] Go take a look at old midterms and see what additional problems you can do
now.
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.