\(\newcommand{\tile}[2]{\left[\frac{\texttt{#1}}{\texttt{#2}}\right]}\)

# Problem: Honey Bunches of Oats

(Sipser 5.3) Find a match in the following instance of the Post Correspondence Problem:

\[ \left\{ \tile{ab}{abab}, \tile{b}{a}, \tile{aba}{b}, \tile{aa}{a} \right\}. \]

(Sipser 5.17) Show that the PCP problem is

*decidable*over the unary alphabet \(\Sigma = \{\, a \,\}\).(

*Hint*: With one symbol, you can safely consider the*number*of symbols on the top and bottom of each tile. From there, think about fractionsâ€¦)