Definition: Let M = (Q, S, R, s, F) be a FA. The language accepted by M, L(M), is defined as:
L(M) = {w: w Î S*, sw |–* f,  f Î F}
Accepted Language
M = (Q, S, R, s, F):
 sa1a2…an |– q1a2…an |– … |– qn-1an |– qn
w
if qn Î F then w Î L(M);
otherwise, w Ï L(M)
M accepts w if it can completely read w by a sequence of moves from s to a final state
 Gist:
16/29