1. Let R1 = ((a+b)cc∗b∗(a+c))∗ and R2 = a∗(a+b)c∗b(a+b) betworegularexpressions. Forparts(a)to(c),please type each word on a new line. The notation w1 ·w2 denotes concatenation of words w1 and w2, and wr denotes the word obtained by reversing w. (a)→ [E1-Q1a.txt] Give two non-empty words w1 and w2 such that{w1,w2}⊆ L(R1)∩L(R2). (2marks) (b)→ [E1-Q1b.txt] Give two non-empty words w3 and w4 such that{w3,w4}⊆ L(R1)L(R2). (2marks) (c)→ [E1-Q1c.txt] Give two non-empty words w5 and w6 such that{w5,w6}⊆ L(R2)L(R1). (2marks) (d)→ [E1-Q1d.txt] Give a non-empty word w7 ∈ L(R1) such that w7 ·wr 7 ∈ L(R1). (1mark) (e)→ [E1-Q1e.txt] Give a non-empty word w8 ∈ L(R1) such that w8 ·wr 8 6∈ L(R1). (1mark) (f)→ [E1-Q1f.txt] Give a regular expression R3 such that L(R3) = L(R1)∪L(R2). (1marks) (g)→ [E1-Q1g.txt] Give a regular expression R4 such that L(R4) = L(R1)∩L(R2). (3marks) 2. Give regular expressions for the following languages. (a)→ [E1-Q2a.txt] L1 = {a2nb3m+1 | n ≥ 1,m ≥ 0}. (2marks) (b)→ [E1-Q2b.txt] L2 = L1 (where L stands for the complement of L; we assume alphabet Σ = {a,b}). (2marks) (c)→ [E1-Q2c.txt] L3 = {w | w ∈{a,c}∗,|w| mod 5 = 0},|w|denotes the length of word w. (2marks) (d)→ [E1-Q2d.txt] L4 = {wcn | n > 0,w ∈{a,b}∗{b,c}∗} ∩ {bw | w ∈{a,c}∗}. (2marks) 3. Let R1 and R2 be two regular expressions over a non-empty alphabet Σ. Determine, formally, whether the following statements are true. That is, if it is true, provide a proof; otherwise provide a counter example. (a) If we assume that L(R1) ⊂ L(R2), then it is the case that L(R∗ 1) ⊂ L(R∗ 2). (4marks) (b) Is the converse of the above statement true? That is, if L(R∗ 1) ⊂ L(R∗ 2), then L(R1) ⊂ L(R2).
AssignmentTutorOnline
The post provide a proof appeared first on My Blog.