Homework 3
Last updated: Thu, 4 Nov 2021 14:27:29 -0400
Out: Mon Sept 27, 00:00 EST Due: Sun Oct 3, 23:59 EST
This assignment explores regular expressions, and also non-regular languages.
Homework Problems
Let’s Create Some Regular Expressions (4 points)
The Decode Operation (6 points)
A Non-Regular Language? (5 points)
Regular or Not? (4 + 4 = 8 points)
README (2 point)
Total: 25 points
Submitting
Submit your solution to this assignment in Gradescope hw3. Please assign each page to the correct problem.
A submission must include a README containing the required information, in addition to the solution to the problems. Please make sure all solutions are legible.
1 Let’s Create Some Regular Expressions
\left\{w\mid w\textrm{ has at least three }\texttt{1}s\right\}
\left\{w\mid w\textrm{ has at least three }\texttt{1}s\textrm{ or has at least two }\texttt{0}s\right\}
\left\{w\mid w\textrm{ is an even length string }\right\}
\left\{w\mid w\textrm{ starts and ends with the same symbol }\right\} (assume \Sigma = \left\{\texttt{a},\texttt{b}\right\})
If you wish, you may use the following additional regular expression notations:
\Sigma = any char in the alphabet of the language
\Sigma^* = zero or more of any char in the alphabet of the language
2 The Decode Operation
Show that the \textrm{\footnotesize{DECODE}} operation is closed for regular languages, where:
\textrm{\footnotesize{DECODE}}(L) =\left\{\textrm{\footnotesize{DECODE}}_{str}(w)\mid w\in L\right\}
L is a language, w = w_1\cdots w_n represents strings in L, \textrm{\footnotesize{DECODE}}_{str}(w) = \textrm{\footnotesize{DECODE}}_{char}(w_1)\cdots\textrm{\footnotesize{DECODE}}_{char}(w_n), and \textrm{\footnotesize{DECODE}}_{char}:\Sigma\rightarrow\Sigma is some function mapping each character in the language’s alphabet to another character in the alphabet.
Use proof by induction on regular expressions.
Example:
If:
\textrm{\footnotesize{DECODE}}_{char}(\texttt{c}) = \texttt{s}
\textrm{\footnotesize{DECODE}}_{char}(\texttt{h}) = \texttt{g}
\textrm{\footnotesize{DECODE}}_{char}(\texttt{s}) = \texttt{j}
\textrm{\footnotesize{DECODE}}_{char}(\texttt{a}) = \texttt{e}
\textrm{\footnotesize{DECODE}}_{char}(\texttt{t}) = \texttt{t}
Then: \textrm{\footnotesize{DECODE}}(\left\{\texttt{cat},\texttt{hat},\texttt{sat}\right\}) =\left\{\texttt{set},\texttt{get},\texttt{jet}\right\}
3 A Non-Regular Language?
Prove that the following language EQ, with alphabet \Sigma = \left\{0,1,\texttt{=}\right\}, is not regular:
EQ = \left\{x\texttt{==}y\mid\textrm{where }x\textrm{ and }y\textrm{ are equal binary numbers }\right\}
Use the Pumping Lemma and proof by contradiction. Make sure your proof has all the correct components.
4 Regular or Not?
For each of the following languages, prove whether they are regular or non-regular.
Use the Myhill-Nerode Theorem.
You may assume the languages use an alphabet \Sigma = \left\{0,1\right\}.
L_1 = \left\{w\mid\textrm{where }w\textrm{ ends in } 00\right\}
L_2 = \left\{ww\mid\textrm{where }w\in\Sigma^*\right\}