Week 5 Lecture 1

Are regular languages are closed under symmetric difference (i.e. a string \(s\) is in exactly one of \(L_1\) and \(L_2\), denoted \(L_1 \Delta L_2\)).

Are regular languages are closed under superset?

Show that the language \(L = {a^n b^n}\) is non-regular.

Week 5 Lecture 2

Find a context free grammar for all strings that correctly match ( [ and { brackets.

Find a context free grammar for all palindromes formed within the alphabet abcd

Week 6 Lecture 1

Show that \(PDA \subseteq CFL\)

Show that \(CFL \subseteq PDA\)

Week 7 Lecture 2

See slide 9

Week 8 Lecture 2

See 46:35 in Lecture

Week 9 Lecture 1

What is a decider?

What is a decidable language?

Week 10 Lecture 1

Look through the list of undecidable languages in Lecture 18 and identify those that are recursively enumerable.

A language is decidable if and only if both it and its complement are recursively enumerable.

A language \(L\) is recursively enumerable if and only if there is a decidable two-argument predicate \(P\) such that

\[ x \in L \Leftrightarrow \exists y P(x,y) \]

where \(P\) is sometimes called a verifier. \(y\) here acts like a certificate or evidence. E.g. consider \(L\) to be the set of all real diamonds and \(x\) to be a shiny stone. \(y\) may be a authentic diamond report that with \(P\) an expert diamond seller is able to show that \(x \in L\).

Week 12 Lecture 1

Show that hamiltonian circuits are reducible to SATISFIABILITY.

Chapter 1 Sipser

Corollary 1.40

Prove that a language \(L\) is regular if and only if some nondeterministic finite automaton recognises it