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.