theory of computation 2

Question

how to reduce this type of expression

Comments

prefer to avoid reduction. it may consume time.

better to just check options. this doesn't accept NULL , so eliminate the one that accept NULL , in that way ....

---

can u explain which of  following option will be true

a) set of the string that contain either 'aa' or 'bb' as substring

b) set of string that either begin and end with a or b

c) Set of string that contain atmost one time two consecutive a’s or two consecutive b’s.

d) None of these

---

check one by one

C)saying maximum one time 2 consecutive a or b ....there is in last (a+b)^* which can give as many consecutive a.b as you want. so false

B)string 'a' . begins with a ..so does your language accept this? no so false

A) as there is none of above option so we have to take care whether this include all strings of just subset of what's our actual language is...we then find it true.

Answer 1

Matches with RE: (a+b)*(aa+bb)(a+b)*

Answer 2

see at the very last of the expression it contains (a+b)* so convert this expression to finite automata first and you will come to know the reductive and unnecessary steps there and just remove those and express again.