Express each of these languages over = {0, 1} using a regular expression. a the

Question

Express each of these languages over = {0, 1} using a regular expression.

a the set containing all strings with zero, two, or three symbols

b the set of strings that begin with one 1, followed by one or more 0s, and ending with two 1s

c the set of strings that contain the substring 101 at least twice

d the set of strings containing exactly one 1 and an even number of 0s

Note that the regular expression operators you may use are alternation (a|b, where a and b are regular expressions), concatenation (a·b or just ab), and iteration (a*).

Explanation / Answer

[a] +(0+1)(0+1)+(0+1)(0+1)(0+1)

Explanation - is for zero length string, (0+1) means either 0 or 1, writing twice means that 2 symbols are allowed which means string length 2 and same with (0+1)(0+1)(0+1) also which allows 3 symbols

[b] 1(0)+11

Explanation: Beginning with 1, (0)+ means having at least one 0 and ending with two 1s, 11

[c] (0+1)101(0+1)101(0+1) + (0+1)10101(0+1)

Explanation : Having 101 as substring and it should appear twice means that inbetween those 2 substring we can have any numer of 0s/1s which is the reason why (0+1) added in betweeen two 101s. Considering the later part, it is a special case where 101 substring can come together making (101)01 and 10(101).

[d] (00)*1(00)*

Explanation : We have only one 1 and can have any even number of 0s - (00)* which means 00 can occur any number of times

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.