REGULAR LANGUAGES AND REGULAR EXPRESSIONS (theory of automata)

Question

I am going through book of "introduction to language and the theory of computation by John C martin" chapter # 3 section 3.1. Following exercise, question # 3.7 (i)"The language of all strings containing both bb and aba as sub-strings." this question puzzled me".

here is the expression i made. i do not know its good or wrong:

"(a+b)*((bb(a+b)*aba)+(bb(a+b)*aba))(a+b)*".

I am also confuse with "+" and "|" symbols. I think its same. is not it? (yes?/no?)???

Answer 1

+ and | are actually very different. a+ is the same as writing a(a*). It is telling you write the string one or more times. | is an operator that gives you a choice. (a|b) is telling you to choose a or b.

Your expression that you chose seems correct except that all + should be converted to |.