Let G = (N , T , R, S) be context-free. A non-terminal A is self-embedding if
and only if sAu for some s, u ∈ T .
a) Give a procedure to determine whether A ∈ N is self-embedding.
b) Show that, if G does not have a self-embedding non-terminal, then it is regular.