Which of the following is equivalent to the set described by the regular expression 11∗00∗?

• {1m0m|m>0 is a natural number}

• {1m0n|m,n>0 are natural numbers}

• {1m0m|m≥0 is a natural number}

• {1m0n|m,n≥0 are natural numbers}

Which of the following regular expressions generates the complement of the language generated the regular expression (00+11)∗?

• (00+11)∗(0+1)+(00+11)∗(01+10)(0+1)∗

• (00+11)(0+1)∗+0(00)∗+1(11)∗

• (01+10)(0+1)∗+0+1

• (00+11)(0+1)∗+(0+1)(01+10)∗

Let R and S be two regular expressions. Which of the following is equivalent to the regular expression S(S+RS)∗?

• R(SR+R)∗

• (RR∗S∗S∗)∗

• (S+SR)∗R

• RR∗S(RR∗S)∗

Any regular expression of size n can be converted to an NFA (with ϵ-transitions) having at most (select the smallest possible asymptotic upper bound)

• O(n) states

• O(n2) states

• O(2n) states

• O(1) states

The union of two decidable languages is

• context-free but not necessarily regular

• regular

• decidable but not necessarily context-free

• recognizable but not necessarily decidable