comp2022/2922 Assignment 2 (80 marks) s2 2022

Let Σ = {a, b}. For each of the following languages, provide a nondeterministic finite automaton for that language. No justification is necessary. For full marks, your automaton should use at most the specified number of states. Partial marks will be awarded for larger automata.

1. The set of strings with the property that there are two occurrences of the same letter that are exactly 3 positions apart (i.e. there are exactly 2 letters between them). For example, abaaa ∈ L, ababa  L. (8 states)

2. The set of strings whose length is not divisible by 6 or that contain at least two bs (or both). For example, ab, ababab ∈ L, e, aabaaa  L. (8 states)

Problem 2. (20 marks, 10 marks each)

Let Σ = {a, b}. For each of the following languages, prove that the language is not regular.

1. The set {a2n bn : n ≥ 1}.

2. The set of strings {y0, y1, y2, · · · } where y0  = e, yi  = yi−1ai  if i is an odd positive integer, and yi = yi−1bi if i is an even positive integer. For example, y0 = e, y1 = a, y2 = abb, y3 = abbaaa, y4 = abbaaabbbb, etc.

Problem 3. (20 marks, 5/5/10)

Let Σ  =  {a, b}.  For each of the following languages, provide a deterministic Turing Machine that decides that language.  No justification is necessary.  For full marks, your machines should work for any input and be reasonably efficient. Guidelines on this efficiency will be posted on Ed.

1. The language {an bn+1 : n ≥ 0}.

2. The language from Problem 2, part 2.

3. The  set  of  strings  of the  form  uxu,  where  u, x  ∈ Σ∗ are  strings  and u   e.  For example, bb, abbba, abbab, baaaaaababaa, abbababbab  ∈ L while e, ba, abbab, aaabab, bababbabba  L.

Problem 4.   (30 marks) An implicit string is a way of writing a string where we allow the use of exponents.  For example, (abc)3 b is an implicit string that equals abcabcabcb.  Implicit strings allow us to write very long strings much more concisely, such as

(abc)10000000000000000000000000000000000db

which is too large to store in a modern computer’s memory but can be written in under 100 characters as an implicit string.

An implicit string is given in the form

(x1 )n1 (x2 )n2  . . . (xk)nk

where x1, x2, . . . , xk are (ordinary) strings and n1, n2, . . . , nk are positive integers. Your task is to write code that takes an automaton N and a sequence of implicit strings from stdin, and outputs whether N accepts each of the strings to stdout. Some skeleton code will be provided (in Python) that demonstrates how to han-

dle the input/output.  You may assume that the input is valid.  Your program will not be tested on invalid input.

You are guaranteed that all input automata will have fewer than 100 states, all input implicit strings will have k < 10, and that all resulting strings will be of length less than 262 .

In each subproblem, 50% of the marks will be for DFA cases and 50% will be for

NFA cases.

Here is an explanation of the restrictions:

• ”small string” means that the resulting string will be of length at most 1000

• ”1 symbol” means that the implicit string will be the exponent of a single symbol