Ch.4: Regular Expressions
Week 4 of the book "Automata, Formal Languages, and Turing Machines" by Emre Sermutlu (2020) 4.1. Definition 4.2. Regular Languages and Regular Expressions
53 flashcards · Computer Science · by lakesare
Part of Textbooks › Automata, Formal Languages, and Turing Machines (Emre Sermutlu) · 14 courses
[Definition] What is a regular expression used for?
To describe a language (a set of strings over an alphabet Σ\SigmaΣ ) in a short notation. Example: over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} , the regular expression 0∗10^*10∗1 describes {1,01,001,0001,… }\{1, 01, 001, 0001, \dots\}{1,01,001,0001,…} .
[Definition] Which three operations combine regular expressions into new ones?
Union X∪YX \cup YX∪Y Example: 0∪10 \cup 10∪1 describes {0,1}\{0, 1\}{0,1} . Concatenation X∘YX \circ YX∘Y The symbol ∘\circ∘ is usually omitted: X∘YX \circ YX∘Y is written XYXYXY . Example: (0∪1)1(0 \cup 1)1(0∪1)1 describes {01,11}\{01, 11\}{01,11} . Star X∗X^*X∗ Example: (01)∗(01)^*(01)∗ describes {ε,01,0101,010101,… }\{\varepsilon, 01, 0101, 010101, \dots\}{ε,01,0101,010101,…} . These are the same operations as on languages: a regular expression is read as the language it describes.
[Definition] In regular expressions, what do 00∪1000 \cup 1000∪10 and (001∪111)∗(001 \cup 111)^*(001∪111)∗ stand for?
The languages {00}∪{10}={00,10}\{00\} \cup \{10\} = \{00, 10\}{00}∪{10}={00,10} and {001,111}∗\{001, 111\}^*{001,111}∗ . A string and a set of strings are different things, but a regular expression is used as a shorthand for a language, so the same notation is used for both.
[Definition] What is the formal definition of a regular expression RRR over an alphabet Σ\SigmaΣ ?
RRR is one of: ∅\varnothing∅ , ε\ \varepsilon ε , a\ a a with a∈Σa \in \Sigmaa∈Σ , X∪Y\ X \cup Y X∪Y , X∘Y\ X \circ Y X∘Y , X∗\ X^* X∗ , where XXX and YYY are regular expressions. The first three are the base cases; the last three build larger regular expressions from smaller ones.Example: (0∪1)∗1(0 \cup 1)^*1(0∪1)∗1 is a regular expression: 000 , 111 are base cases, then union, star, concatenation.
[Definition] Operation precedence in regular expressions: star first, concatenation second, union last.
Example: ab∗∪cab^* \cup cab∗∪c means (a(b∗))∪c\big(a(b^*)\big) \cup c(a(b∗))∪c .
[Definition] Where do the implicit parentheses go in ab∗∪cab^* \cup cab∗∪c ?
(a(b∗))∪c\boldsymbol{\big(a(b^*)\big) \cup c}(a(b∗))∪c Star first, concatenation second, union last. So ab∗∪cab^* \cup cab∗∪c is different from a(b∗∪c)a(b^* \cup c)a(b∗∪c) and from (ab)∗∪c(ab)^* \cup c(ab)∗∪c .Example: abbabbabb is in ab∗∪cab^* \cup cab∗∪c ; acacac is in a(b∗∪c)a(b^* \cup c)a(b∗∪c) only; abababababab is in (ab)∗∪c(ab)^* \cup c(ab)∗∪c only.
[Definition] What does a+a^+a+ mean in a regular expression?
One or more copies of aaa : a+={a,aa,aaa,… }=aa∗\ a^+ = \{a, aa, aaa, \dots\} = aa^* a+={a,aa,aaa,…}=aa∗ Like a∗a^*a∗ , but at least one symbol is included, so ε∉a+\varepsilon \notin a^+ε∈/a+ .
[Definition] What is the difference between the regular expressions ∅\varnothing∅ and ε\varepsilonε ?
∅\varnothing∅ describes the language with no string; ε\varepsilonε describes the language with one string, the empty string. Example: 00∪∅={00}00 \cup \varnothing = \{00\}00∪∅={00} , but 00∪ε={00,ε}00 \cup \varepsilon = \{00, \varepsilon\}00∪ε={00,ε} .
[Definition] Which languages do (00∪∅)11(00 \cup \varnothing)11(00∪∅)11 and (00∪ε)11(00 \cup \varepsilon)11(00∪ε)11 describe?
(00∪∅)11=(00 \cup \varnothing)11 = (00∪∅)11= {0011}\{0011\}{0011} ; (00∪ε)11=\ (00 \cup \varepsilon)11 = (00∪ε)11= {0011,11}\{0011, 11\}{0011,11} ∅\varnothing∅ adds no string to the union; ε\varepsilonε adds the empty string, and ε∘11=11\varepsilon \circ 11 = 11ε∘11=11 .
[Definition] Which language does ∅∗\varnothing^*∅∗ describe?
ε\boldsymbol{\varepsilon}ε (the language {ε}\{\varepsilon\}{ε} ) The star of any language contains ε\varepsilonε (zero copies concatenated), and ∅\varnothing∅ has no string to concatenate.
[Definition] Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} . Describe in words the languages 1(0∪1)∗1(0 \cup 1)^*1(0∪1)∗ and 1Σ∗1\Sigma^*1Σ∗ .
Both: the strings that start with 1. In a regular expression, Σ\SigmaΣ stands for the union of all symbols, here 0∪10 \cup 10∪1 .
[Definition] Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} . Describe in words the language Σ∗1Σ∗\Sigma^*1\Sigma^*Σ∗1Σ∗ .
The strings that contain at least one 1. Example: 0010=00⋅1⋅00010 = 00 \cdot 1 \cdot 00010=00⋅1⋅0 is in it; 000000000 is not.
[Definition] Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} . Describe in words the languages 0∗(ε∪1)0∗0^*(\varepsilon \cup 1)0^*0∗(ε∪1)0∗ and 0∗10∗0^*10^*0∗10∗ .
0∗(ε∪1)0∗0^*(\varepsilon \cup 1)0^*0∗(ε∪1)0∗ : at most one 1. 0∗10∗\ 0^*10^* 0∗10∗ : exactly one 1. Example: 000=03⋅ε⋅ε000 = 0^3 \cdot \varepsilon \cdot \varepsilon000=03⋅ε⋅ε is in the first but not the second; 010001000100 is in both.
[Definition] Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} . Describe in words the languages ΣΣΣ\Sigma\Sigma\SigmaΣΣΣ , (ΣΣΣ)∗\ (\Sigma\Sigma\Sigma)^* (ΣΣΣ)∗ and (ΣΣΣ)+(\Sigma\Sigma\Sigma)^+(ΣΣΣ)+ .
ΣΣΣ\Sigma\Sigma\SigmaΣΣΣ : length exactly 3. (ΣΣΣ)∗\ (\Sigma\Sigma\Sigma)^* (ΣΣΣ)∗ : length a multiple of 3. (ΣΣΣ)+\ (\Sigma\Sigma\Sigma)^+ (ΣΣΣ)+ : length a positive multiple of 3. ΣΣΣ\Sigma\Sigma\SigmaΣΣΣ is the same as (0∪1)(0∪1)(0∪1)(0 \cup 1)(0 \cup 1)(0 \cup 1)(0∪1)(0∪1)(0∪1) . The only difference between the last two is ε\varepsilonε (length 0).
[Definition] Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} . Give regular expressions for the strings that start and end with aaaaaaaaa and have length at least 6, and length at least 7.
Length ≥6\ge 6≥6 : aaaΣ∗aaa\boldsymbol{aaa\Sigma^*aaa}aaaΣ∗aaa ; \ length ≥7\ge 7≥7 : aaaΣ+aaa\boldsymbol{aaa\Sigma^+aaa}aaaΣ+aaa Σ+\Sigma^+Σ+ forces at least one symbol between the two blocks of aaaaaaaaa .
[Definition] Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} . Give a regular expression for the strings of length at least 3 that start and end with aaaaaaaaa .
aaaΣ∗aaa∪aaaaa∪aaaa∪aaa\boldsymbol{aaa\Sigma^*aaa \cup aaaaa \cup aaaa \cup aaa}aaaΣ∗aaa∪aaaaa∪aaaa∪aaa Strings shorter than 6 have the starting and ending aaaaaaaaa overlapping: aaaaaaaaaaaaaaa (overlap 1), aaaaaaaaaaaa (overlap 2), aaaaaaaaa (overlap 3).
[Definition] Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} . Give a regular expression for the strings in which no aaa comes after a bbb and no ccc comes before a bbb .
a∗b+c∗∪(a∪c)∗\boldsymbol{a^*b^+c^* \cup (a \cup c)^*}a∗b+c∗∪(a∪c)∗ If the string contains a bbb : only aaa 's before the first bbb , only bbb 's between the first and the last bbb , only ccc 's after the last bbb . If it contains no bbb , both conditions hold for every string over {a,c}\{a, c\}{a,c} .The book answers a∗b∗c∗a^*b^*c^*a∗b∗c∗ , which is right for the reading "first aaa 's, then bbb 's, then ccc 's", but misses e.g. cacaca , which contains no bbb .
[Definition] Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} . Give a regular expression for the strings that do not contain bbbbbb .
(b∪ε)[(a∪c)+b]∗(a∪c)∗\boldsymbol{(b \cup \varepsilon)\big[(a \cup c)^+b\big]^*(a \cup c)^*}(b∪ε)[(a∪c)+b]∗(a∪c)∗ Every bbb except a first one at the very start is preceded by a nonempty block of aaa 's and ccc 's.Example: bacb=b⋅(ac)b⋅εbacb = b \cdot (ac)b \cdot \varepsilonbacb=b⋅(ac)b⋅ε ; ca=ε⋅ε⋅ca\ ca = \varepsilon \cdot \varepsilon \cdot ca ca=ε⋅ε⋅ca .
[Definition] Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} . Give a regular expression for the strings that start and end with the same symbol.
aΣ∗a∪bΣ∗b∪cΣ∗c∪a∪b∪c\boldsymbol{a\Sigma^*a \cup b\Sigma^*b \cup c\Sigma^*c \cup a \cup b \cup c}aΣ∗a∪bΣ∗b∪cΣ∗c∪a∪b∪c The strings of length 1 start and end with the same symbol too, and aΣ∗aa\Sigma^*aaΣ∗a only has strings of length at least 2.
[Definition] Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} . Give a regular expression for the strings that contain an even number of ccc 's.
[(a∪b)∗c(a∪b)∗c(a∪b)∗]∗∪(a∪b)∗\boldsymbol{\big[(a \cup b)^*c(a \cup b)^*c(a \cup b)^*\big]^* \cup (a \cup b)^*}[(a∪b)∗c(a∪b)∗c(a∪b)∗]∗∪(a∪b)∗ Each block inside the star contains exactly two ccc 's; (a∪b)∗(a \cup b)^*(a∪b)∗ adds the strings with no ccc that the star misses (e.g. ababab ).Example: acbcaacbcaacbca is one block: a⋅c⋅b⋅c⋅aa \cdot c \cdot b \cdot c \cdot aa⋅c⋅b⋅c⋅a .
[Definition] Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} . Give regular expressions for the strings of length exactly 2, and of length at most 2.
Exactly 2: (a∪b∪c)(a∪b∪c)\boldsymbol{(a \cup b \cup c)(a \cup b \cup c)}(a∪b∪c)(a∪b∪c) ; \ at most 2: (a∪b∪c∪ε)(a∪b∪c∪ε)\boldsymbol{(a \cup b \cup c \cup \varepsilon)(a \cup b \cup c \cup \varepsilon)}(a∪b∪c∪ε)(a∪b∪c∪ε) Choosing ε\varepsilonε in one or both factors gives the strings of length 1 and 0.
[Definition] Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} . Give a regular expression for the strings that contain at least two ccc 's.
Σ∗cΣ∗cΣ∗\boldsymbol{\Sigma^*c\Sigma^*c\Sigma^*}Σ∗cΣ∗cΣ∗ Example: acbca=a⋅c⋅b⋅c⋅aacbca = a \cdot c \cdot b \cdot c \cdot aacbca=a⋅c⋅b⋅c⋅a .
[Definition] Σ={a,b}\Sigma = \{a, b\}Σ={a,b} . Give the state diagram of an NFA and of a DFA recognizing the language a∗b∗a^*b^*a∗b∗ .
NFA: an aaa -loop state, an ε\varepsilonε -arrow to a bbb -loop state, both accepting. DFA: reading aaa after a bbb leads to the rejecting trap state q3q_3q3 . The NFA is simpler and shows the structure of the regular expression better.
[Definition] Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} . Give a regular expression for the language of this NFA.
a∗(bb∪cbc)\boldsymbol{a^*(bb \cup cbc)}a∗(bb∪cbc) The aaa -loop at the start state gives a∗a^*a∗ ; the two paths to the accept state give bbbbbb and cbccbccbc .
[Definition] Give an NFA recognizing the language of (b∪aa)∗(bb)∗(ε∪aba)(b \cup aa)^*(bb)^*(\varepsilon \cup aba)(b∪aa)∗(bb)∗(ε∪aba) .
Three stages in series, joined by ε\varepsilonε -arrows; inside each stage, the parts of a union in parallel. Stage 1: bbb -loop and aaaaaa -cycle at the start state. Stage 2: bbbbbb -cycle. Stage 3: abaabaaba path or ε\varepsilonε -arrow to the accept state.
[Regular Languages and Expressions] Which languages can be described by a regular expression?
Exactly the regular languages: a language is regular if and only if some regular expression describes it. Regular language: recognized by some DFA, or equivalently some NFA.The proof has two parts: regular expression to NFA, and NFA to regular expression.
[Regular Languages and Expressions] In the proof that every regular expression describes a regular language, which NFAs are used for the base cases ∅\varnothing∅ , ε\varepsilonε and a∈Σa \in \Sigmaa∈Σ ?
R=∅R = \varnothingR=∅ One start state, which is not accepting: no string is accepted. R=εR = \varepsilonR=ε One start state, which is accepting and has no arrows: only ε\varepsilonε is accepted. R=aR = aR=a A start state with an aaa -arrow to an accept state: only aaa is accepted.
[Regular Languages and Expressions] Given NFAs for regular expressions XXX and YYY .How is an NFA built for X∪YX \cup YX∪Y , for X∘YX \circ YX∘Y , and for X∗X^*X∗ ?
X∪YX \cup YX∪Y Connect the two NFAs in parallel: a new start state with ε\varepsilonε -arrows to the start states of both. X∘YX \circ YX∘Y Connect the two NFAs in series: ε\varepsilonε -arrows from the accept states of XXX to the start state of YYY ; only the accept states of YYY stay accepting. X∗X^*X∗ ε\varepsilonε -arrows from the accept states of XXX back to its start state, plus an extra start state, which is accepting, with an ε\varepsilonε -arrow to the old start state. With the base cas…
[Regular Languages and Expressions] In the NFA construction for X∗X^*X∗ , why add a new accepting start state instead of making the old start state accepting?
The old start state may have incoming arrows, so making it accepting can accept strings not in X∗X^*X∗ . The new start state is accepting so that ε∈X∗\varepsilon \in X^*ε∈X∗ is accepted, and no arrow enters it.Example: X=(ab)∗aX = (ab)^*aX=(ab)∗a has an NFA q0→aq1q_0 \overset{a}{\to} q_1q0→aq1 , q1→bq0q_1 \overset{b}{\to} q_0q1→bq0 , q0→aq2q_0 \overset{a}{\to} q_2q0→aq2 , q2q_2q2 accepting. Making q0q_0q0 accepting accepts ab∉X∗ab \notin X^*ab∈/X∗ .
[Regular Languages and Expressions] Build an NFA for (a∪bb)∗(a \cup bb)^*(a∪bb)∗ with the construction from regular expressions (NFAs for aaa and bbbbbb , then union, then star).
The NFAs for aaa and bbbbbb in parallel after a branching state, ε\varepsilonε -arrows from both accept states back to that state, and a new accepting start state. bbbbbb is built as b∘bb \circ bb∘b : two bbb -arrows joined by an ε\varepsilonε -arrow.
[Regular Languages and Expressions] Give an NFA with two states recognizing (a∪bb)∗(a \cup bb)^*(a∪bb)∗ .
An accepting start state with an aaa -loop, and a bbb -arrow to a second state and a bbb -arrow back. The NFA from the general construction has 8 states: it works, but it is not the simplest one.
[Regular Languages and Expressions] To turn an NFA into a regular expression, the proof uses a modified kind of NFA. Which four conditions does it satisfy?
One accept state There is a single accept state, distinct from the start state. Start state No arrows enter the start state. Accept state No arrows leave the accept state. Labels Arrow labels are regular expressions. Example:
[Regular Languages and Expressions] How is any NFA put into the modified form (single accept state distinct from the start state, no arrows into the start state, none out of the accept state)?
Add a new start state and a new accept state, connected to the old ones by ε\varepsilonε -arrows. New start →ε\overset{\varepsilon}{\to}→ε old start; every old accept state →ε\overset{\varepsilon}{\to}→ε new accept state, and the old accept states stop accepting.
[Regular Languages and Expressions] What is the idea of state elimination for turning an NFA (in the modified form) into a regular expression?
Remove the intermediate states one by one until only the start and accept state remain; the label of the last arrow is the regular expression. At each removal, arrows are relabelled so that the language of the machine stays the same.
[Regular Languages and Expressions] p,q,rp, q, rp,q,r are states, and the arrows p→rp \to rp→r , p→qp \to qp→q , q→qq \to qq→q , q→rq \to rq→r have labels W,X,Y,ZW, X, Y, ZW,X,Y,Z (regular expressions).In state elimination, how is p→rp \to rp→r relabelled when qqq is removed?
W∪XY∗Z\boldsymbol{W \cup XY^*Z}W∪XY∗Z A path from ppp to rrr through qqq reads XXX , then YYY any number of times, then ZZZ ; WWW is the direct arrow. Example: W=111W = 111W=111 , X=0X = 0X=0 , Y=1Y = 1Y=1 , Z=00Z = 00Z=00 give 111∪01∗00111 \cup 01^*00111∪01∗00 .
[Regular Languages and Expressions] In state elimination, when a state qqq is removed, which arrows must be relabelled?
The arrow p→rp \to rp→r for every pair of states p,rp, rp,r with an arrow p→qp \to qp→q and an arrow q→rq \to rq→r , including p=rp = rp=r . If there is no arrow p→rp \to rp→r , the new label is just XY∗ZXY^*ZXY∗Z ; if qqq has no loop, Y∗Y^*Y∗ is left out.Example: q3→dq4→dq3q_3 \overset{d}{\to} q_4 \overset{d}{\to} q_3q3→dq4→dq3 : removing q4q_4q4 gives a loop at q3q_3q3 labelled dddddd .
[Regular Languages and Expressions] Find a regular expression for the language of this NFA.
a(dd∪bc∗a)∗\boldsymbol{a(dd \cup bc^*a)^*}a(dd∪bc∗a)∗ Every accepted string starts with aaa (to q3q_3q3 ); at q3q_3q3 it can repeat dddddd (to q4q_4q4 and back) or bc∗abc^*abc∗a (through q2q_2q2 and q1q_1q1 ).Equivalent answers: [a(dd)∗bc∗]∗a(dd)∗[a(dd)^*bc^*]^*a(dd)^*[a(dd)∗bc∗]∗a(dd)∗ and a[(dd)∗(bc∗a)∗]∗a[(dd)^*(bc^*a)^*]^*a[(dd)∗(bc∗a)∗]∗ .
[Regular Languages and Expressions] NFA: start q1q_1q1 , accept q3q_3q3 ; arrows q1→aq3q_1 \overset{a}{\to} q_3q1→aq3 , q3→bq2q_3 \overset{b}{\to} q_2q3→bq2 , q2→cq2q_2 \overset{c}{\to} q_2q2→cq2 , q2→εq1q_2 \overset{\varepsilon}{\to} q_1q2→εq1 , q3→dq4q_3 \overset{d}{\to} q_4q3→dq4 , q4→dq3q_4 \overset{d}{\to} q_3q4→dq3 .After adding a new start and accept state with ε\varepsilonε -arrows, what are the steps of state elimination in the order q4q_4q4 , q2q_2q2 , q1q_1q1 ?
Remove q4q_4q4 : loop dddddd at q3q_3q3 . Remove q2q_2q2 : q3→bc∗q1q_3 \overset{bc^*}{\to} q_1q3→bc∗q1 . Remove q1q_1q1 : start →aq3\overset{a}{\to} q_3→aq3 , loop dd∪bc∗add \cup bc^*add∪bc∗a at q3q_3q3 . Removing q3q_3q3 last leaves one arrow: a(dd∪bc∗a)∗a(dd \cup bc^*a)^*a(dd∪bc∗a)∗ .
[Regular Languages and Expressions] Give an NFA recognizing (ab)∗(a∗∪bbb)∗(aba∪ε)(ab)^*(a^* \cup bbb)^*(aba \cup \varepsilon)(ab)∗(a∗∪bbb)∗(aba∪ε) .
Start state with an ababab -cycle; ε\varepsilonε -arrow to an accepting state with an aaa -loop and a bbbbbbbbb -cycle; from there an abaabaaba path to a second accept state. (a∗∪bbb)∗=(a∪bbb)∗(a^* \cup bbb)^* = (a \cup bbb)^*(a∗∪bbb)∗=(a∪bbb)∗ , so a single aaa -loop is enough for the middle part.
[Exercises] LLL is described by 1(01)∗∪0(11)∗1(01)^* \cup 0(11)^*1(01)∗∪0(11)∗ over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} . Are 101011010110101 , 0\ 0 0 , 101010\ 101010 101010 , 0111\ 0111 0111 in LLL ?
101011010110101 : yes; 0\ 0 0 : yes; 101010\ 101010 101010 : no; 0111\ 0111 0111 : no 10101=1⋅01⋅0110101 = 1 \cdot 01 \cdot 0110101=1⋅01⋅01 ; 0=0⋅ε\ 0 = 0 \cdot \varepsilon 0=0⋅ε ; strings in 1(01)∗1(01)^*1(01)∗ have odd length, 101010101010101010 has length 6; 0111=0⋅1110111 = 0 \cdot 1110111=0⋅111 and 111∉(11)∗111 \notin (11)^*111∈/(11)∗ .
[Exercises] LLL is described by (Σ∗aΣ∗a∪bb)b∗(\Sigma^*a\Sigma^*a \cup bb)b^*(Σ∗aΣ∗a∪bb)b∗ over Σ={a,b}\Sigma = \{a, b\}Σ={a,b} . Are aabbbbbaabbbbbaabbbbb , bbbba\ bbbba bbbba , bbababab\ bbababab bbababab , a\ a a in LLL ?
aabbbbbaabbbbbaabbbbb : yes; bbbba\ bbbba bbbba : no; bbababab\ bbababab bbababab : yes; a\ a a : no LLL = strings with at least two aaa 's, plus bbbbbb and bbbbbb followed by bbb 's. aabbbbb=aa⋅bbbbb\ aabbbbb = aa \cdot bbbbb aabbbbb=aa⋅bbbbb ; bbababab=bbababa⋅b\ bbababab = bbababa \cdot b bbababab=bbababa⋅b ; bbbbabbbbabbbba and aaa have only one aaa .
[Exercises] Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} . Describe in words the language 0(10)∗∪0(10)∗1∪1(01)∗∪1(01)∗00(10)^* \cup 0(10)^*1 \cup 1(01)^* \cup 1(01)^*00(10)∗∪0(10)∗1∪1(01)∗∪1(01)∗0 .
Alternating sequences of 0's and 1's of length at least 1 (no 000000 and no 111111 ). The four parts: start with 0 or 1, end with 0 or 1.
[Exercises] Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} . Describe in words the language 0(ΣΣ)∗Σ∪1(ΣΣ)∗0(\Sigma\Sigma)^*\Sigma \cup 1(\Sigma\Sigma)^*0(ΣΣ)∗Σ∪1(ΣΣ)∗ .
Strings of length at least 1: those starting with 0 have even length, those starting with 1 have odd length. 1+1+2k1 + 1 + 2k1+1+2k is even and 1+2k1 + 2k1+2k is odd.
[Exercises] Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} . Describe in words the language (0∪1)∗0(0∪1)∗1(0∪1)∗∪(0∪1)∗1(0∪1)∗0(0∪1)∗(0 \cup 1)^*0(0 \cup 1)^*1(0 \cup 1)^* \cup (0 \cup 1)^*1(0 \cup 1)^*0(0 \cup 1)^*(0∪1)∗0(0∪1)∗1(0∪1)∗∪(0∪1)∗1(0∪1)∗0(0∪1)∗ .
Strings that contain at least one 0 and at least one 1. The first part has a 0 before a 1, the second a 1 before a 0.
[Exercises] Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} . Give a regular expression for the strings of odd length, at least 3, whose first and last symbols are ccc .
cΣ(ΣΣ)∗c\boldsymbol{c\Sigma(\Sigma\Sigma)^*c}cΣ(ΣΣ)∗c The length is 2+1+2k2 + 1 + 2k2+1+2k , odd and at least 3.
[Exercises] Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} . Give a regular expression for the strings of length at least 2 that start with aaa or bbb , end with ccc , and contain neither ababab nor bababa .
(a+c+∪b+c+)+\boldsymbol{(a^+c^+ \cup b^+c^+)^+}(a+c+∪b+c+)+ A block of aaa 's and a block of bbb 's can never be next to each other, so every such block is followed by a block of ccc 's.Example: aacbcc=aac⋅bccaacbcc = aac \cdot bccaacbcc=aac⋅bcc .
[Exercises] Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} . Give a regular expression for the strings that contain at most two ccc 's.
(a∪b)∗(c∪ε)(a∪b)∗(c∪ε)(a∪b)∗\boldsymbol{(a \cup b)^*(c \cup \varepsilon)(a \cup b)^*(c \cup \varepsilon)(a \cup b)^*}(a∪b)∗(c∪ε)(a∪b)∗(c∪ε)(a∪b)∗ Each (c∪ε)(c \cup \varepsilon)(c∪ε) contributes zero or one ccc .
[Exercises] Find a regular expression for the language of this NFA.
a∗b(aba∪baa)∗(ab∪ba)\boldsymbol{a^*b(aba \cup baa)^*(ab \cup ba)}a∗b(aba∪baa)∗(ab∪ba) From q2q_2q2 to q4q_4q4 : ababab (via q3q_3q3 ) or bababa (via q5q_5q5 ); the arrow q4→aq2q_4 \overset{a}{\to} q_2q4→aq2 makes the cycles abaabaaba and baabaabaa at q2q_2q2 .
[Exercises] Find a regular expression for the language of this NFA.
(a∪bb∪bab)∗b(ε∪ba∗b)\boldsymbol{(a \cup bb \cup bab)^*b(\varepsilon \cup ba^*b)}(a∪bb∪bab)∗b(ε∪ba∗b) Cycles at the start state: aaa , bbbbbb (lower left), babbabbab (through the first accept state). Then bbb to the first accept state, optionally followed by ba∗bba^*bba∗b to the second.
[Exercises] Find a regular expression for the language of this NFA.
(ba)∗[ba∪(a∪bb)(a∪b)]b\boldsymbol{(ba)^*\big[ba \cup (a \cup bb)(a \cup b)\big]b}(ba)∗[ba∪(a∪bb)(a∪b)]b (ba)∗(ba)^*(ba)∗ : cycles between the first two states. Then to the state before the accept state: directly by bababa , or via the top state by a(a∪b)a(a \cup b)a(a∪b) or bb(a∪b)bb(a \cup b)bb(a∪b) . Last, bbb .
[Exercises] Find a regular expression for the language of this NFA.
(a∪aba∪abaaba)(cba∪cbaaba)∗\boldsymbol{(a \cup aba \cup abaaba)(cba \cup cbaaba)^*}(a∪aba∪abaaba)(cba∪cbaaba)∗ Start to accept: aaa , or a baa\,baaba then ε\varepsilonε , or a ba abaa\,ba\,abaabaaba . Cycles at the accept state: ccc then bababa or baababaababaaba .
[Exercises] Give an NFA recognizing (aaa∪aba)∗bab∗(aaa \cup aba)^*bab^*(aaa∪aba)∗bab∗ .
A start state with a 3-cycle labelled aaa , a,b\ a{,}b a,b , a\ a a , then bbb , aaa to an accept state with a bbb -loop. aaa∪aba=a(a∪b)aaaa \cup aba = a(a \cup b)aaaa∪aba=a(a∪b)a , so one cycle covers both.
[Exercises] Give an NFA with two states recognizing (a∪aba∪ba)∗(a \cup aba \cup ba)^*(a∪aba∪ba)∗ .
An accepting start state with an aaa -loop, a bbb -arrow to a second state and an aaa -arrow back. aba=a⋅baaba = a \cdot baaba=a⋅ba , so (a∪aba∪ba)∗=(a∪ba)∗(a \cup aba \cup ba)^* = (a \cup ba)^*(a∪aba∪ba)∗=(a∪ba)∗ .