计算机理论 CS3331 – Assignment 1 Regular Languages

计算理论 Theory of Computation

CS3331 – Assignment 1 – 2018 Regular Languages

Due: Tuesday, Oct 16, 2018 (Latest to submit: Friday, Oct 19)

  1. (60pt) For each of the following languages, either prove it is not regular or do the following:
    • construct a NDFSM for it
    • convert the NDFSM into a regular expression (horrible regular expressions from Jflap are accepted

      only when no obvious ones can be found)

    • convert the NDFSM into a DFSM (Note that you do not have to include trap/dead states)
    • minimize the DFSM
    1. (a)  {w ∈ {a, b}∗ : w has abba as a substring}.
    2. (b)  {w ∈ {a, b}∗ : w does not have abba as a substring}.
    3. (c)  {w ∈ {0, 1}∗ : if w contains the substring 01 then |w| is even}.
    4. (d)  {w∈{0,1}∗ : w=wR}.

    (e){w∈{a,b}∗ :wdoesnotendinaa}.

    1. (f)  {w ∈ {a,b}∗ : w contains exactly three more a’s than b’s}.
    2. (g)  {w = yxyz : x,y,z ∈ {0,1}+}.
    3. (h)  {w ∈ Σ∗ : w is a Java comment}, where Σ is the ASCII alphabet and Java comments are of two

      types: /* … comment … */; // … comment … \n.

  2. (20pt) The Pattern Searching problem is: Given two strings p, T ∈ Σ∗ (the pattern and the text), find all occurrences of p in T. It can be solved in time O(|T|) by constructing a DFSM for the language Σ∗p and then run the text T through it; every time the machine is in an accepting state, we report the end of an occurrence of the pattern. Construct the minimal DFSM for the pattern p = ananea. (Show also your NDFSM.)
  3. (20pt) Show that the following problem is decidable: Given a FSM M and a regular expression α, it is true that both L(M) and L(α) are finite and α generates at least one string that M does not accept?

Note well: You may submit your assignment in one of two ways:

  • Ideally, submit your solution as a pdf file on OWL (scanned written assignments are fine). Submitted

    this way, assignments submitted by 11:59 pm Oct 19 will be accepted.

  • Otherwise staple your assignment and hand in solutions in class or to the 3331 dropbox (locker #306, across from the elevator on the 3rd floor of Middlesex College). Submitted this way, assignments will not be accepted after 5:00 pm Oct 19.

    Note well: You are allowed to use Jflap to solve the assignment. But remember that Jflap will not be allowed during the midterm exam.

Related Posts