1.

2.

Consider the following NFA N=(Q,,,s,F), where F={s}. Apply the subset construction to N to get a DFA M=(Q,,,s,F), where Q={,{s},{q},{r},{s,q},{s,r},{q,r}, {s,q,r}} Mark all the elements of F. {s,r} { r } {s,q,r} {q,r} {q} {s,q} \{s\} Let G be a grammar where all rules are of one of the following three forms: A or AbC for terminal b and variable C, or ACb for terminal b and variable C. Then L(G) is decided by some DFA. L(G) is decided by some regex. L(G) is decided by some NFA. L(G) is decided by some RRG. L(G) is context-free