Formal Language and Automata Homework 4

   

  • Submission Guideline: Upload your homework file (hw4_[your student id].doc, hw4_[your student id].hwp or hw4_[your student id].pdf) to online Eruri classroom. You are allowed to write down your answers either in Korean or English at your convenience.
  • Deadline : 18:00 PM, Tuesday, October 5

       

Please feel free to leave your questions about homework problems in the online Piazza classroom.

       

  1. Prove that the following are not regular languages.

a) ${\{0^n10^n \mid n \geq 1}\}$.

b) $\{0^n 1^m 2^n \mid$ $n$ and $m$ are arbitary integers $\}$.

c) ${\{0^n1^{2n} \mid n \geq 1}\}$.

   

  1. Prove that the following are not regular languages.

a) $\{0^n \mid$ $n$ is a perfect square $\}$.

b) $\{0^n \mid$ $n$ is a perfect cube $\}$.

c) $\{0^n \mid$ $n$ is a power of $2$ $\}$.

d) The set of string of $0$’s and $1$’s whose length is a perfect square.

   

  1. When we try to apply the pumping lemma to a regular language, the adversary wins, and we cannot complete the proof. Show what goes wrong when we choose $L$ to be one of the following languages.

a) ${\{00,11}\}$

b) $(00+11)^*$

   

  1. Suppose $L$ is a regular language with alphabet $\Sigma$. Given an algorithm to tell whether $L = \Sigma^*$, i.e, all strings over its alphabet.

   

  1. Give an algorithm to tell whether two regular languages $L_1$ and $L_2$ have at least one string in common.

   

6.

  state $0$ $1$
$\rightarrow$ $A$ $B$ $A$
  $B$ $A$ $C$
  $C$ $D$ $B$
* $D$ $D$ $A$
  $E$ $D$ $F$
  $F$ $G$ $E$
  $G$ $F$ $G$
  $H$ $G$ $D$

​ a) Draw the table of distinguishabilities for this automaton.

​ b) Construct the minimum-state equivalent DFA.

   

7.

  state $0$ $1$
$\rightarrow$ $A$ $B$ $E$
  $B$ $C$ $F$
* $C$ $D$ $H$
  $D$ $E$ $H$
  $E$ $F$ $I$
* $F$ $G$ $B$
  $G$ $H$ $B$
  $H$ $I$ $C$
* $I$ $A$ $E$

​a) Draw the table of distinguishabilities for this automaton.

b) Construct the minimum-state equivalent DFA.