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, [email protected] 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, [email protected] 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, [email protected] 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, [email protected] 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, [email protected] 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, [email protected] 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, [email protected] 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, [email protected] 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.
Collepals.com Plagiarism Free Papers
Are you looking for custom essay writing service or even dissertation writing services? Just request for our write my paper service, and we'll match you with the best essay writer in your subject! With an exceptional team of professional academic experts in a wide range of subjects, we can guarantee you an unrivaled quality of custom-written papers.
Get ZERO PLAGIARISM, HUMAN WRITTEN ESSAYS
Why Hire Collepals.com writers to do your paper?
Quality- We are experienced and have access to ample research materials.
We write plagiarism Free Content
Confidential- We never share or sell your personal information to third parties.
Support-Chat with us today! We are always waiting to answer all your questions.
