T Naughton, NUIM
Back to CS355 home

Lab sheet 5 - Context-free languages

For each of the following languages, construct a context-free grammar that generates it, and construct a pushdown automaton that accepts (recognises) it. You will be tested individually at the end of the lab.

Language 5.1 L = {w : w {0, 1}*, w begins with a 1}.

Language 5.2 L = {w : w {0, 1}*, w ends with 10}.

Language 5.3 L = {w : w {0, 1}*, w contains exactly one 1}.

Language 5.4 L = {w : w {0, 1}*, w contains exactly one 1 that is always at the beginning of the word}.

Language 5.5 L = {w : w {0, 1}*, w contains at most one 1, and if it has a 1 it is positioned at the beginning of the word}.

Language 5.6 L = {w : w {0, 1}*, w contains a 1 at the beginning and at the end of the word}.

Language 5.7 L = {w#w^R : w {0, 1}*}.

Language 5.8 L = {0ⁱ1^j : i > j}.

Language 5.9 L = {0ⁱ1^j2^k : i = j or j = k}.