Lab 5 - 09/9 Wednesday


Language transformations

The first part of the lab is about language transformations which is a powerful tool to reason about languages. The basic fact (which hopefuly managed to cover in lecture) is that NFAs and DFAs are equivalent in terms of the languages they can recognize. This means that for every NFA, there exists a DFA that recognizes the same language, and vice versa.

A more general fact is that if I take a DFA or NFA and apply some transformation to it, the resulting automaton will recognize a language that is related to the original language in some way. For example, if I take a DFA and reverse all of its transitions (and do some bookkeeping to make sure result is still a proper DFA) the resulting automaton will recognize the reverse of the original language.

This is immensely useful for reasoning about languages. For example, if I want to prove that some arbitrary operation done on a regular language results in a regular language, then I can take a DFA (whatever that maybe, I don’t need to know) that recognizes it, apply some transformation to it, which results in a new automaton (typically an NFA) that recognizes the new language, then I can conclude that the new language is regular because it is recognized by a NFA.

Required reading: Ch. 4, JEMC. Pay special attention to Section 4.9.

  1. Let \(\Sigma =\) {0,1}. Prove that the following language \(L_1\) is regular, given that language \(L\) is regular.

    \[L_1 = \left\{ \operatorname{flipOdd}(w) \; \mid \; w \in L \right\} \]

    The function flipOdd will apply a binary NOT on every odd-indexed bit (assume zero-indexing). For example, if w=01011100, then flipOdd(w) = 00001001.

  2. Let \(\Sigma =\) {0,1}. Prove that the following language cycle(L) is regular, given that language \(L\) is regular where: \[ \operatorname{cycle}(L) = \left\{ xy \; \mid \; x, y \in \Sigma^*, \; yx \in L\right\} \] In other words, the new language consists of rotations of string from a regular language.

  3. Prove that the language insert1(L) defined as: \[ \operatorname{insert1}(L):= \set{x1y \; \mid \; xy\in L}\] is regular. Intuitively, insert1(L) is the set of all strings that can be obtained from strings in \(L\) by inserting exactly one 1 (where?) into the string.

Automata conversions

The second part of the lab is about converting between different automata representations of regular languages. The main goal is to get you familiar with the algorithms and the process of converting between different types of equivalent automata (and RegExes).

  1. Consider the NFA you obtained in Lab 4, Problem 5.
    1. Convert the NFA to a DFA using the incremental subset construction algorithm. Your DFA should have four states, all reachable from the start state.
    2. Convert the DFA you constructed above into a regular expression using the state elimination algorithm.
  2. Consider the regular expression: (0*1+01*)*
    1. Convert the regular expression into an NFA using Thompson’s algorithm.
    2. Convert the NFA you obtained in the previous problem into a DFA using the incremental subset construction algorithm. Your DFA should have four states, all reachable from the start state.
    3. Convert the DFA you constructed above into a regular expression using the state elimination algorithm. You should not get the same RegEx you started with.