For each of the following languages over the alphabet {0,1}, give a regular expr

Question

For each of the following languages over the alphabet {0,1}, give a regular expression that describes that language, and briefly argue why your expression is correct.

(a) All strings except 010.

(b) All strings that end in 10 and contain 101 as a substring.

(c) All strings in which every nonempty maximal substring of 1s is of length divisible by 3. Forinstance 0110 and 101110 are not in the language while 11101111110 is.

(d) All strings that do not contain the substring 010.

(e) All strings that do not contain the subsequence 100.

Explanation / Answer

a. 1*(0* 111*)* 0*1*

language does not contain substring 010 because after first occurance of 0 it must be followed by atleast two one's(1's).

b. (0+1)* (101) (0+1)* 10

In this langauge , strings may begin with any number of zers or 1's followed by substring 101 and followed with any number of zers or 1's and must end with 10.

The highlighted pattern in regular expression appears in all strings of the language.

c) 0* (111)+ 0* (111)*

generates all strings may begin with 0's , followed by one or more multiples of three ones may end with 0's or again multiples of three ones.

d) 1*(0* 111*)* 0*1*

language does not contain substring 010 because after first occurance of 0 it must be followed by atleast two one's(1's).

e) 0* 1*(01)*1*

Initially zero's may be followed by any number of 1's but 1 's must be followed by single zero , which restricts the occurance of two zero's after occurance of 1.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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