Let R, S, T, U be regexes.
Prove or disprove that :
if S*(R + S) === R*(R + S)
then, S* === R*
Please answer the question by the following format:
example:Let L be a language over Σ = {0, 1}, construct a DFSA that accepts it, as well as a regex that denotes it for the following language
L = {x ∈ Σ* : x ends in 01 or 10 or 00 or 11 }.
Answer:
DFSA: attatched
State Invariant(x, q0)
q0: iff x = ε
q1: iff x has one digit
q2: iff x ends with one of: 00, 01, 10, 11
regex: (0+1)*(0+1)(0+1)
This regex states that the string can have any number of 0s and 1s, as long as it ends with in 00, 01, 10, 11.
