Your Location is: Home > Regular-language

What is the regular languages that are equivalent to the given regular language: (0 + 1)*1(0 + 1)*

From: Athens View: 2312 qwerty1s 

Question

I am learning automata theory. I have answered the question wrongly three times, and I don't know the right answers. Please help me.

The target language is (0+1)*1(0+1)*. The choices are:

A) (01+11)*(0+1)*
B) (0+1)*(10+11+1)(0+1)*
C) (1+0)*1(1+0)*
D) (0+1)*(0+1)(0+1)*

Multiple choices are allowed, if there's more than one equivalent language.

Best answer

Consider your options, and either factor them into a form that looks like your target, or find a word that is in one language but not the other:

Target: (0+1)*1(0+1)*, this is the language of all words over {0,1} containing at least one 1.

A) (01+11)*(0+1)*, this does not include at least one 1. For example, the empty string is in A but not in the target.

B) (0+1)*(10+11+1)(0+1)*, looking specifically at the 10+11+1 part, which can be factored into 1(0+1+ε). (0+1+ε)(0+1)* is not different from (0+1)*.

C) (1+0)*1(1+0)*, this is just the target with 0+1 replaced with 1+0. The union operation + is commutative.

D) (0+1)*(0+1)(0+1)*, this language includes the word 0 which is not in the target.