COS3701 ASSIGNMENT 2
Question 1
Variables:
• S: Start state
• A: We’ve just seen an a
• AB: We’ve just seen ab — be cautious here; next a would complete aba (invalid)
• F: Any continuation after safe strings
S → aA | bS | ε
A → aA | bAB | ε
AB → bS // prevent aba by only allowing b here
Explanation:
• S allows any combination, but if a is seen, move to A.
• In A, seeing b means we may be forming ab, so we go to AB.
• In AB, the only safe continuation is another b; a would form aba, which is not
allowed.
Question 1
Variables:
• S: Start state
• A: We’ve just seen an a
• AB: We’ve just seen ab — be cautious here; next a would complete aba (invalid)
• F: Any continuation after safe strings
S → aA | bS | ε
A → aA | bAB | ε
AB → bS // prevent aba by only allowing b here
Explanation:
• S allows any combination, but if a is seen, move to A.
• In A, seeing b means we may be forming ab, so we go to AB.
• In AB, the only safe continuation is another b; a would form aba, which is not
allowed.
