ISI2025-MCS-PCB (Non-CS) | Question: 9

Question

1. Let $L$ be a language over an alphabet $\{a, b\}$ such that the empty string does not belong to $L$ and the first and the last letters of every string in $L$ are the same. Draw a DFA to accept the language $L$. Argue whether your DFA is the minimal one accepting $L$.
2. Prove that the language $L=\left\{a^{m} b^{n} \mid m \neq n\right\}$ is not regular. You may use the fact that the language $\left\{a^{n} b^{n} \mid n \geq 0\right\}$ is not regular.