ITEC 420 - Homework Assignments


Fall 2019


Updates - Last modified


DO NOT do the homeworks that have a red background!

They are from last semester.

The current homework is always in green.




Homework 1a
  • Due: Monday 9/2/19, at the beginning of class. Late assignments not accepted.
  • Make sure that you justify your answers, where appropriate
  • Please put your solutions in order and clearly label each with the problem number.
  • Always be clear about what kind of object your answer is (eg a set, an ordered pair) and use the right kind of notation (eg {} for sets and () for ordered tuples).

  • The problems are based on Appendix A of the text:
    1. Express the set A without using the cross product: A = {1, 2} x {a, b} x {d, e}. [Hint: What kinds of things are the elements of A? Once you know that, just list the elements, as a set.]
    2. Express the set B defined below without using the cross product: B = {1, 2} x {a, b} x { }. [Hint: the last set in the definition is empty. Now apply that fact to the definition of cross product.]
    3. Draw a lattice that shows the proper subset relation among the 8 elements of the power set of {1,2,3}. In your lattice, if $P\subset Q$, with no proper subsets between them, then write Q somewhere above P and with a line from P to Q.
    4. Describe, in words, the set C [assume $\mathbb{N}$ is the set of natural numbers (ie the nonnegative integers)]: Your answer will start: C is the set of natural numbers x such that ... $$ C = \{x \in \mathbb{N} :\exists y \in \mathbb{N} (y \lt 12 \wedge (y+5 = x))\}$$
    5. List the elements, as a set, of the set C from the previous problem (your answer will look something like C = {19, 43, 55}).
    6. Let the set of letters P = {a, c, e, g, w, y}. Express the set P using set builder notation: P = [Hint: Consider the alphabet position of the letters, and also use some of the other problems in this homework as a pattern.]
    7. Let the set A be you and two of your friends, and let the set B be the set of your car and the cars of these friends (Assume that your friends have different makes of cars and if you or a friend doesn't have a car, simply choose a fantasy car.) Give example relations in $A \times B$ that meet the criteria listed below. List the relations as sets of ordered pairs. Each relation must have at least two elements. To save writing, you may use initials or first names for people and abbreviations for cars. For each function, indicate whether it is a total or partial function.
      1. A relation that is not a function.
      2. A function that is 1:1 and onto.
      3. A function that is 1:1 and not onto.
      4. A function that is onto but not 1:1.
      You might want to ponder what each of these relations might represent.


Homework 1b
  • Due Wednesday 9/4/19, by 4:00 p.m.. Late assignments not accepted.
  • Make sure that you justify your answers.
  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • Some problems are based on Appendix A of the text:
    1. Express the proposition below in English. (Your answer should start: "There exists a natural number x, ... " or "There is a natural number x"). $$ \exists x\in\mathbb{N}(x = -x)$$
    2. Express the proposition below in English. (Your answer should start: "For every natural number x, ... " or "For all natural numbers x"). $$ \forall x\in\mathbb{N}(\forall y\in\mathbb{N}(\exists z\in\mathbb{N}(x = y + z)))$$
    3. Express the set below in English. (Your answer should start: "G is the set of natural numbers x"). $$ G = \{ x\in\mathbb{N}: \exists y\in\mathbb{N}(\forall z\in\mathbb{N}(x < y \wedge y < z))\}$$
    4. Let set $D=\{1, 4, 7, 10, 13, \dots\}$, where the dots represent numbers that follow the obvious pattern. Express this set in the form $D = \{x\in \mathbb{N} : P(x) \}$, where you replace $P(x)$ with some proposition of x (ie a statement that is true or false of x, such as x is even). You answer will look like $\{x\in \mathbb{N}: \dots \}$ where you fill in the set of dots, as, for example, in the previous problem.

    5. Express the result in 5 or fewer symbols: $2^{60} \times 2^{4} = $ [Hint: Question: Express 10×16 in 3 symbols (instead of 5). Answer: 160]
    6. Express the result in 5 or fewer symbols: How many distinct numbers can be represented with 64 bits?


Homework 1c
  • Due Friday 9/6/19, by 4:00 p.m.. Late assignments not accepted.
  • Make sure that you justify your answers.
  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • Some problems are based on Appendix A of the text:
    1. Prove that the set of multiples of 3 (ie ..., -6, -3, 0, 3, 6, ...) are countable.

    2. In class we discussed the fact that |A × B| = |A| × |B|. Although this seems very reasonable, we never proved it. Let's prove something simpler: Use induction to prove that if A = {x,y,z} then |A × B| = 3 × |B|. Make sure that you set up your induction as in the $\displaystyle\sum_{i=1}^n$ example done in class, showing each step. [Hint: Use induction on the size of B.]


Homework 2
  • Due Date: Tuesday 9/10/19 at 12:30 p.m.. Late assignments not accepted.

  • Make sure that you justify your answers.

  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • The problems are based on the Chapter 2 Exercises which are on pages 19 and 20. The first and second problems are modifications of one from the text, the third problem is not in the text, and the rest are from the text.

    1. Modification of problem 2.2: Give the 3 shortest strings that are in the language and the four (4) shortest strings that are not in the language. [Do not do parts a, b, c, and d of problem 2.2 as written.]

    2. Another modification of problem 2.2: Write an English description of the set of strings defined by the expression L1L2, where L1 and L2 are defined in problem 2.2. Your answer will be something like "The language L1L2 is the set all strings with ...". [Do not do parts a, b, c, and d of problem 2.2 as written.]

    3. Let L1 = {apple, pear} and L2 = {pie, cake, ε}. List the elements of L1L2 in lexicographic order. [Be careful!]

    4. 2.6.a [N.B. Do NOT simply restate the math; instead describe, in English, the strings in the language]
    5. 2.6.b [N.B. as above in 2.6.a]
    6. 2.6.c [N.B. as above in 2.6.a]

    7. 2.8.a [Note for 2.8: If the statement is false, you may, if you prefer, use a counter-example to prove that it's false. If it is true, simply explain why you think it's true rather than giving a formal proof. Hint: A majority are false.]
    8. 2.8.e [Note: as above in 2.8.a]
    9. 2.8.g [Note: as above in 2.8.a]
    10. 2.8.l [Note: as above in 2.8.a]


Homework 3a
  • Due Date: Tuesday 9/17/19, 12:30 p.m. Late assignments not accepted.
  • Due Date: Monday 9/16/19, in class. Late assignments not accepted.

  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • For these problems, you only need to justify your answers when the problem says to do so. Also, you are only required to refer to the formal definition in the first, second, and last problems.

  • Except where specified, you don't have to justify these answers. Just work the problems.

  • The first three problems are based on Exercise 5.1 on hardcopy page 121 (pdf page 87):
    1. After making the three changes listed below to the machine shown in Exercise 5.1, give the formal definition of the machine. In other words, give the 5-tuple that defines the machine. In still more words: give s; the sets K, Σ, and A; and δ. You can give δ as a table or as a set of mappings. But first, make the following three changes in the machine:
      1. Change state 2 to NOT be an accept state.
      2. Change state 5 to NOT be an accept state.
        • Thus, state 3 is the only accept state.
      3. Define δ(6, b) = 5

    2. Using the machine (as modified above) shown in Exercise 5.1, do the following:
      1. Give the computation determined by the string aabaa
        • Hint: The computation consists of a sequence of six configurations, separated by the yields turnstile. Each configuration is an ordered pair: (current state, remaining input).
      2. State whether or not the string is accepted, and use the formal definitions of the machine and of accepting a string to justify your answer.
        • Hint: Your answer will begin with "The string aabaa is/isn't accepted because ....

    3. Using the machine (as modified above) shown in problem 5.1, give a clear, short (about 20 words) English description of the language accepted by the machine.
      • Hints: Can the machine exit state 5? You will want to use the words "even" and/or "odd" in your answer. You will also use the phrases "zero or more" and/or "one or more".

    4. Draw a Deterministic FSM (DFSM) that accepts the language {w ∈ {a,b}* : w begins with ab}
      • N.B. The FSMs that we have seen so far are Deterministic, because their transitions are defined by a (total) function. Next we will be working with Nondeterministic FSM (NDFSM or NFSM), whose transitions are defined by a relation. Do not give a Nondeterministic FSM, for any answer in this set of problems.
    5. Draw a DFSM that accepts the language {w ∈ {a,b}* : w does NOT begin with ab}
      • Hint: Once you have solved problem 4, this problem has a no-brain solution.

    6. Draw a DFSM that accepts the language {w ∈ {a,b}* : |w| ≥ 2 and w has different first and last letters.}
    7. Draw a DFSM that accepts the language {w ∈ {a,b}* : w contains aa somewhere}

    8. Draw a DFSM that accepts the language {ε}. Assume the alphabet is {a,b}. Make sure that your machine is complete (ie has all transitions).
    9. Draw a DFSM that accepts the language {}. Assume the alphabet is {a,b}. Make sure that your machine is complete (ie has all transitions).

    10. What must be true about a machine (ie DFSM) that accepts ε? Answer in terms of the 5-tuple that defines that machine.


Homework 3b
  • Due Date: Wednesday 9/17/19 in class. Late assignments not accepted.
    1. As you know, a common definition of multiplication is that it is repeated addition, and so 5*2 means 2+2+2+2+2. But now let's (temporarily) forget that definition, and use induction to prove that for all positive $n$, $$\displaystyle \underbrace{2+2+\dots+2}_{n \text{ times}} = n\cdot 2$$ To prove this you will need your times tables and some basic rules of multiplication and addition, so don't forget them too. We stick with positive $n$ so that we don't have to contemplate adding 2 to itself zero times.


Homework 4a
  • Due Date: Monday 9/23/19, in class. Late assignments not accepted.

  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • No justification needed for this assignment. You can simply show your answers.
  • The problems are based on Chapter 5:

    1. Give the lexicographic ordering of the concatenation of languages L1 and L2 (ie L1 L2) where L1={apple, pch, pr} and L2={ε, pi, juice}.
      • In case you're wondering, "pch", "pr", and "pi" are abbreviations for the words "peach", "pear", and "pie". You can enjoy dreaming of peaches, pears, and pies while doing the assignment, but make sure that you use the abbreviations in your answer.

    2. Draw a DFSM (N.B. Deterministic!) for the following language over $\Sigma = \{a, b\}: L_2 = \{\epsilon, a\}$
    3. Draw a DFSM (N.B. Deterministic!) for the following language over $\Sigma = \{a, b\}: L_3 = \Sigma^* - \{\epsilon\}$ [That is, the language that contains all strings except the empty string] [N.B. This problem originally defined $L_3 \text{ as } \Sigma^* - \epsilon$, which has a type error.]

    4. Draw a NDFSM (N.B. Nondeterministic, here and for the rest of this homework) that accepts the language $ L_4 = \{w \in \{a,b\}^* : w \text{ contains } ba \vee w \text{ contains both } aa \text{ and } bb\} $

    5. Draw a NDFSM that has exactly five (5) states and that accepts the language $ L_5 = \{ w : w=abab^n \vee w=aba^n \text{, with } n\ge 0\}$

    6. Draw a NDFSM that has exactly three (3) states and that accepts the language $ L_6 = \{ ab, abc\}^* $. Hint: The first few strings, in lexicographic order: $\epsilon, ab, abc, abab, ababc, abcab, ababab, abcabc, abababc, ababcab, abcabab$.

    7. Draw a NDFSM that has exactly four (4) states and that accepts the language $ L_7 = \{ w : w=a^m \vee w=b^na \text{, with } m\ge 0 \wedge n\ge 1\}$

    8. Draw a NDFSM that has exactly three (3) states and that accepts the language $ L_8 = \{ w : w=a^k \vee w=b^ma^n \text{, with } k\ge 1 \wedge m,n\ge 0\}$


Homework 4b
  • Due Date: Tuesday 9/24/19, 12:30 p.m. Late assignments not accepted.
  • No justification needed for this assignment. You can simply show your answers.
  • The problems is based on the Chapter 5 exercises on hardcover page 123 (pdf page 89):

    1. Problem 5.9.a with one change: Add a loop transition from state q1 to itself on the symbol zero (0). Your answer should be similar to what we did in class and it should show the following:

      1. a table for the NDFA that shows, for each state q, the transitions from state q on each alphabet symbol and that also shows eps(q). Your table will have a row for each state q, and it will have 3 columns: one for Δ(q, 0), one for Δ(q, 1), and one for eps(q).

      2. a table that shows δ for the DFA (ie the transitions for all needed states and all alphabet symbols). Your table will have a row for each DFA state (ie each set of NDFA states) and a column for each of the two input symbols. Hint: You do not have to show all possible DFA states, and your DFA will end up having fewer than 6 states.

      3. a diagram of the resulting DFA.


Homework 5a
  • Due Date: Thursday 10/3/19, 12:30 p.m. Due Date: Thursday 10/4/19, 12:30 p.m. Late assignments not accepted.

  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • The problems are based on Chapter 6 and involve regular expressions (REs):
    1. For each of the following regular expressions, give three (3) strings that are in the language that is defined by that RE and give three (3) strings that are NOT in the language that is defined by that RE. If there are not three such strings, state that fact. Whenever possible, choose strings that are as small as possible (ie length 2 or below).
      1. (ε ∪ a)b
      2. a* ∪ b*
      3. (a ∪ b)*

    2. Describe in English the languages generated by the following REs. Do not simply transcribe the RE; instead, find a concise English description of the strings in the language. Answers will be around 8-12 (or once 15) words long.
      1. (a (a ∪ bb)* )*
      2. ( (a ∪ b) a)*
      3. b*(ab+)*
      4. a(a ∪ b)*a ∪ b(a ∪ b)*b ∪ a ∪ b

    3. Give REs for each of the following languages over Σ = {a, b}:
      1. Strings containing exactly 2 b's or exactly three b's.

      2. Strings containing exactly 0 or 1 b's, and if the string does contain a single b, then that b appears at either the beginning or the end of the string
        Strings containing exactly 0 or 1 b's and any b appears at an end of the string

      3. Strings containing no consecutive a's
      4. Every string contains at least one double letter. Clarification: aaa, bbb, aaba are in the language, and a and aba are not.
      5. No string contains a double letter (ie strings in the language contain neither aa nor bb as a substring).
      6. No string contains ab.


Homework 5b
  • Due Date: Friday 10/4/19, 4:00 p.m. Due Date: Friday 10/5/19, 4:00 p.m. Late assignments not accepted.

  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • The problem is based on Chapter 6 and involves regular expressions (REs):
    1. Follow the algorithm for converting a RE to a FSM and convert b ∪ (ε ∪ b)* to a FSM. Make sure that you follow the algorithm precisely, showing any and all new epsilon transitions and new states.


Homework 5c
  • Due Date: Monday 10/7/19, 4:00 p.m. Due Date: Monday 10/8/19, 4:00 p.m. Late assignments not accepted.

  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • The problem is based on Chapter 6 and involves regular expressions (REs):
    1. Do the following using the diagram below:
      1. Add an φ (ie RE for empty SET) transition between states 1 and 4.
      2. Use the algorithm discussed in class to rip state 2 and show the resulting machine. (Hint: make sure that you show the complete RE on ALL transitions.)
      3. Use the algorithm discussed in class to rip state 3 and show the resulting machine. (Hint: make sure that you show the complete RE on ALL transitions.)
      4. It would be good to do a little testing to verify that your RE is correct. To that end, do the following:
        1. Write down three strings that are accepted by the machine and generated by the RE.
        2. Write down three strings that are NOT accepted by the machine and NOT generated by the RE
        Your strings should have some variety so that they give you some confidence that the RE is correct.


    2. N.B. The diagram on the right is the same as the one on the left, except that the symbols have subscripts so that it is easier to tell the a's and b's apart in the regular expressions. Please use this version, if possible, but there is no need to redo the assignment if you've already finished it with the original version.


Homework 6a
  • Due Date: In class, Monday 10/14/19. Late assignments not accepted.

  • Please make sure that you number all problems (eg 6a.1, 6a.2) and put them in order.
  • The problems are based on Chapter 7 (but parse trees are probably in chapter 11).
  • For all of your grammars, follow the convention that the start symbol is the LHS of your first rule.

  • First some warm-up problems:
    1. Give a Regular Grammar for the language $L_1=\{a,b\}^*$
    2. Give a Regular Grammar for the language $L_2=\{a,b\}^+$
    3. Give a Regular Grammar for the language $L_3=\{w\in\{a,b\}^*: |w| \text{ is even} \} $
    4. Give a Regular Grammar for the language $L_4=\{w\in\{a,b\}^*: |w| \text{ is odd} \}$

  • Now for some more interesting problems:
    1. Give a Regular Grammar for the language $L_5=\{w\in\{a,b\}^*: \#_a(w) \text{ is even and } \#_b(w) \text{ is odd }\} $
      • Hint: The key to solving this one is first realizing that several (ie ≥ 3) variables are needed, and second figuring out exactly what kind of strings are generated by each variable. Once you've figured that out, then the actual grammar is fairly easy.

    2. Give a Regular Grammar for the language $L_6=\{w\in\{a,b\}^*: w \text{ does NOT end in } aa \} $
      1. First, create the grammar, without creating a FSM (you will learn more by doing this first).
      2. Once you have a grammar, create the FSM for $L_6$ L7
      3. Is your grammar correct? If not, write down the grammar corresponding to your FSM.

    3. For the language $L_7=\{w\in\{a,b\}^*: w \text{ does NOT contain the string } aabb \} $ L8={w∈{a,b}*: Every a is immediately followed by one or more b's} do the following:
      1. First draw the FSM for this language
      2. Now give the grammar that corresponds to your FSM.
      3. Show a derivation for the string $baaba$
      4. Show, as far as you can, a derivation for the string $baabb$. Your derivation will get stuck because $baabb\notin L_8$
      5. Draw the parse tree for the derivation of the string $baaba$

  • Comment and hints:
    • The original version of language L7 was wrong.
    • Remember: Regular grammars only (this actually simplifies things).
    • Think about what each veriable derives.

    • A parse tree is a graphical representation of a derivation that, as we will see, has some significant benefits. A compiler builds a parse tree as an intermediate form when it compiles a program.

      Building the Parse Tree for the derivation of string w: The root of the tree is start symbol, S. Build the tree by adding children to some variable V that is a leaf in the tree. (But, of course, after this step, V is no longer a leaf.) The new children of V are the symbols of x in the rule V → x (thus, the number of children of V is |x|). Draw a line from V to EACH of V's children (ie to each symbol in x). Repeat adding children to variables until there are no more variables that are leaves.

      When the tree is done, the internal nodes are all variables, the leaves are all terminals, and the string w can be read across the leaves of the tree. As a check, the number of internal nodes in the finished tree should equal the number of steps in the derivation S ⇒* w since each expansion of a variable to its RHS in the tree corresponds to one step in the derivation. Of course, at each step you must choose the correct rule that leads to w (not x, which I said in an email) being on the leaves!

      .



Homework 6b
  • Due Date: In class, Friday 10/18/19. Late assignments not accepted.

  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • Some of the problems are from the Chapter 11 Exercises on pages 245 and 246 (178-9 of pdf):
    1. In Exercise 11.1 do parts i, ii, iii, and a Revised iv of a and d (but not b and c). [In other words, do a and d (parts i,ii,iii, Revised iv). Do not do b, do not do c, and don't do the book's part iv.]
      • Revised iv: Give a regular grammar for the language.
      • In part ii, it should say "whichever is fewer".
      • In part iii, there is a right paren missing before the comma.

    2. Give a CFG for the language $\{w\in\{a,b\}^*: w=w^R\}$ (This one should be really easy.)

    3. Using the grammar from Exercise 11.3 (ie S→0S1|SS|10),
      1. give a leftmost derivation of the string 00 0101 1011. (Spaces are added to ease reading; they are not part of the string.)
      2. give a rightmost derivation of the string 00 0101 1011. (Spaces are added to ease reading; they are not part of the string.)
      3. give a parse tree for the string in parts a and b (the parts a and b immediately above, not the one in the text)



Homework 6c
  • Final version: Added one more question: adding exponentiation to the expression grammar.

  • Due Date: In class, Monday 10/21/19. Late assignments not accepted.

  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • Some of the problems are from the Chapter 11 Exercises on pages 245 and 246 (178-9 pdf):
    1. Give a CFG for the language $\{a^mb^n: 0 \le m\le n \wedge n-m \textrm{ is even}\}$

    2. Let G be the ambiguous grammar from Example 11.19 (not Exercise 11.19), except assume that productions produce the terminals {a, b, c, d} instead of id. Draw two different parse trees for the string a * b + c + d.

    3. Let G' be the unambiguous grammar from Example 11.19 (not Exercise 11.19), except assume that productions produce the terminals {a, b, c, d, e} instead of id. Do the following for the string a + b + c * d * e:
      1. Give a leftmost derivation of the string
      2. Give a rightmost derivation of the string
      3. Give a parse tree of the string

    4. Give a parse tree of the string a + b * (c + d) * e. Use the grammar from the previous problem (ie unambiguous expression grammar from Example 11.19).

    5. Start with the unambiguous expression grammar from Example 11.19 and modify the grammar to include an exponentiation operator that has HIGHER precedence than * and that is RIGHT associative. Use a caret (ie ^) or up arrow (ie ↑) for the new operator. Of course, parentheses should still have highest precedence.

      For example, for the expression 2+3*4↑2, the grammar should produce a tree that causes the expression to evaluate to 2+3*16 = 50 (assuming that integers are terminals).

      Try to work this one on your own, without using one of the easily findable solutions. If you do resort to finding the answer somewhere, make sure that you include the reference.



Homework 7a
  • Due Date: Friday 10/25/19 in class. Late assignments not accepted.
  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.
  • Unless specified otherwise, PDA's should be natural, not the result of using a grammar to PDA algorithm.
  • For all problems, unless otherwise stated:
    • Deterministic PDA's are to have no choices, but they can, of course, use ε.
    • Nondeterministic PDA's should not use $\epsilon/\epsilon/\epsilon$ as a transition.
    • Pay close attention to whether or not variables such as n can be 0.
    • In your answers you can simply draw the machines; you don't have to formally specify the machine.

  • The problems are from Chapter 11:
    1. Give a DETERMINISTIC PDA for the language $L_1=\{a^nw\in \{a,b\}^*:n\gt 0 \wedge |w|=n\wedge w \text{ starts with } b \}$

    2. Give a DETERMINISTIC PDA for the language $L_2=\{a^mb^nc^{m+n}: m,n\ge 0 \}$

    3. Give a DETERMINISTIC PDA for the language $L_3=\{a^nb^{2n}: n\ge 0 \}$

    4. Give a PDA for the language $L_4=\{wa^n\in \{a,b\}^*:n\ge 0\wedge |w|=n \}$

    5. Give a PDA for the language $L_5=\{w\in\{a,b\}^*: \#_a(w)=\#_b(w) \wedge \text{ in every prefix } p \text{ of } w, \#_a(p)\ge\#_b(p) \}$ (ie there are never more b's than a's when reading left to right}) (Hint: This one is really, really, trivially easy if you make good use of nondeterminism.)
      • No wait, you don't even need to use nondeterminism; it's easy deterministically!


Homework 7b
  • DRAFT: Will probably change a little.
  • Due Date: Wednesay 10/30/19 in class. Late assignments not accepted.

  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • For all problems, unless otherwise stated:
    • Deterministic PDA's are to have no choices, but they can, or course, use ε.
    • Nondeterministic PDA's should not use $\epsilon/\epsilon/\epsilon$ as a transition.
    • Pay close attention to whether or not variables such as n can be 0.

  • The problems are from Chapter 11:
    1. Give a DETERMINISTIC PDA for the language $L_6=\{a^mb^n: 0 \le m\le n \wedge (n-m) \text{ is even} \}$
      DO NOT DO THIS ONE: $L_6=\{a^mb^nc^{m+n}: m\ge n\ge 0 \wedge (m-n)\equiv0\mod 2 \}$
    2. Give a DETERMINISTIC PDA for the language $L_7=\{w\$: w\in \{a,b\}^* \wedge \#_a(W)=\#_b(W) \}$
    3. Give a PDA for the language $L_8=\{a^mb^{m+n}c^n: m\gt 0, n\ge 0 \}$ (Notice >)
    4. Give a PDA for the language $L_9=\{a^mb^{m+n}c^n: m\ge 0, n\ge 0 \}$ (Notice ≥)
    5. Give a PDA for the language $L_{10}=\{a^mb^na^nb^m: m\ge 0, n\ge 0 \}$

    6. Show the top down parse of the string "a * b + c" using the machine defined for the non-ambiguous expression grammar, as defined in the powerpoint notes. Follow the format of the example using columns for transition, unread input, and stack. Use the same numbers for the rules as are given in the notes, and indicate which side of the stack is the top.

    7. Show the bottom up parse of the string "a * b + c" using the machine defined for the non-ambiguous expression grammar, as defined in the powerpoint notes. Follow the format of the example using columns for action, stack, unread input, and RM derivation. Use the same numbers for the rules as are given in the notes, and indicate which side of the stack is the top.


Homework 8a
  • Due Date: Monday 11/11/19, in class. Late assignments not accepted.
  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • Some of the problems are from the Chapter 17 Exercises on pages 407 - 409 (pdf: 298-300):
    1. 17.1.a
    2. 17.1.b

    3. Use the macro language to draw a deterministic TM to decide the language $\{a^p b^q c^r d^s: p, q, r, s \ge 1 \}$
    4. Use the macro language to draw a deterministic TM to decide the language $\{a^p b^q c^r d^s: p, q, r, s \ge 0 \}$
  • Notes:
    • For 17.1, give a short description of what each machine accomplishes. That is, describe what is on the tape after the computation. Also describe where the resulting output string is on the tape in relation to where the input string was on the tape (eg the output string begins 2 spaces to the left of its original beginning).
      It would be a good idea to also describe, briefly, how the machine works (eg changes all a's to 1's) - but do NOT just put its detailed actions into words (eg scan right looking for ...).
      You can assume that the input on the tape is a string of a's and b's (with no embedded blanks) and that the read head starts on the square to the left of the input string.
    • The structure of the machine in 17.1.a may not be clear. The R_blank is executed once, and then an L machine is executed. After this L, symbols a and b go into loops, and these loops return to the L, which is executed again. The R_blank is executed only once, and it is not part of any loop.
    • You should draw your machines with no more than a total of one crossing of transition lines. To avoid crossings completely, one of your machines can use either two y states or two n states. You can also avoid crossings by leaving out some common transitions, and describing in a few words what transitions are missing.


Homework 8b
  • Due Date: Friday 11/15/19. Problem 5 is due in class. Problems 6 and 7 are due at 3:30 p.m. Late assignments not accepted.
  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • The problems are based on the Chapter 17:

    1. Use the macro TM language to write a decider for the language L={x - y = z : x,y,z ∈ 1+}. To clarify: the input alphabet for this language is Σ={-,=,1} and "11-111=1"∈ L. Quotation marks added for clarity; they're not part of the string. Blanks aren't part of the string, either.
      • Hint: This is very similar to the first problem in HW 8a.
      • This machine will be used in problem 8, in the next set.

    2. Consider the encoded DTM <M1> below in which $\Sigma=\{a,b\}$ and $\Gamma=\{\square, a, b, \$\}$. Using Examples 17.19 and 17.20 as a pattern, do the following:
      1. Complete the table below which shows the encoding of the tape symbols.
        Symbol Encoding
        $\square$
        a
        b
        $
      2. Draw the machine that the encoding below represents.
      3. Precisely and concisely describe the language accepted by M1.
        • Hint: In the next question you can discover one of the strings that's in the language.
      Machine Encoding:
         <M1> = (q000, a00, Y011, a00, R),
                (q000, a01, q001, a11, R),
                (q000, a10, N100, a10, R),
                (q000, a11, q000, a11, R),
      
                (q001, a00, N100, a00, R),
                (q001, a01, q001, a01, R),
                (q001, a10, q010, a11, L),
                (q001, a11, q001, a11, R),
      
                (q010, a00, q000, a00, R),
                (q010, a01, q010, a01, L),
                (q010, a10, N100, a10, R),
                (q010, a11, q010, a11, L)
             
    3. Consider the language L = {<M, w> : M accepts w}. One string in this language is <M1,ab> = <M1>,a01a10, where <M1> is the encoding of machine M1, as given above.
      1. Give another two strings in this language, following the pattern above (ie < M1, w> = <M1>,z, where z ∈ {a,b}*).
      2. Show a string <M1,w> that is NOT in the language, following the pattern (ie < M1, w> = <M1>,z, where z ∈ {a,b}*).
      • Hint: This problem is very easy once you know the language; you just have to apply definitions.


Homework 8c
  • Due Date: Monday 11/18/19. Due at 3:30 p.m. Late assignments not accepted.
  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • Some of the problems are from the Chapter 17 Exercises on pages 407 - 409 (pdf: 298-300):

    1. Use the macro TM language to write a Decider for the language L = {x - y = z : x,y,z ∈ 1+ and where x,y,z are considered to be unary numbers such that x - y = z}. To clarify: the input alphabet for this language is Σ = {-, =, 1}. Blanks are added for clarity; they're no part of the strings.
      • Your machine should start by calling the machine from problem 5 above to make sure that the input is in the right format (ie x - y = z where x,y,z are in 1+).

    2. Problem 8 in the Chapter 17 exercises (ie find a ND TM for ww).

      • N.B. The solution to problem 17.8 is extremely simple, if you make use of the power of non-determinism. You do not need to write out the machine in detail. Instead simply give the steps that implement the strategy for solving the problem. You can simply list the steps in English, or you can show them in a simple machine. Your steps can call machines from the text to accomplish the subtasks of your strategy. You can also invent and define, in English, machines to call if you like. Again, the solution is extremely easy if you make good use of other machines and of non-determinism. If your steps directly use a loop, then you probably haven't harnessed nondeterminism. You should probably consider the example of the nondeterministic machine that checks if a binary number is composite.

Homework 9a
  • Due Date: Thursday or Friday 11/21 or 22/19, 3:30 p.m. Late assignments not accepted.
    • My preference is Thursday, but you, as a class, can decide whether it's due on Thursday or Friday. If Thursday, then I will return them Friday.
  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

    1. Draw a diagram of a Transformation machine T2 that has the specification given below.
      Your answer should follow the pattern of the Transformation machine T shown in the figure in Example 17.21 in section 17.6.3 page 404 (295 pdf) of the text. This figure is also around slide 33 (the last slide) in the powerpoints Ch17c. (In the context of this problem, T stands for Transformation, not for Trouble.)
      Transformation machine T2 should operate as follows:
      • Input to T2: an encoded TM <M1>
      • Output from T2: an encoded TM <M2>
        • Such that M2(w) = M1(ww)
      • Thus, T2 must create machine M2 such that M2 duplicates its input string and then runs M1 on the duplicated string.
      • You can use any of the standard machines (eg a copy machine that transforms w into ww) as long as you specify precisely what each machine does (including specifying the starting and ending location of the machine's read/write head).
      • Note that the work of this assignment is drawing, TM M2 , similar to the diagram in Example 17.21. As shown in the Example, you can draw TM T2 simply as a box labeled T2.

    2. Well, we need more than one question, so: Tell me one enjoyable and/or interesting thing that you are planning to do over Thanksgiving (other than working on your next 420 homework assignment; I already know that you'll be enjoying doing that :).


Homework 9b
  • Due Date: Wednesday, 12/4/19 in class. Late assignments not accepted.
  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.
  • Some of the problems are from the Chapter 20 exercises starting on page 445 (325 pdf) and the Chapter 21 Exercises starting on page 483 (354 pdf):

    1. Exercise 20.9
      • Make sure that you start with $n=0$, that is start by enumerating the empty tape (ie the empty string)
      • Make sure that you look at the Printing subroutine P that is described in Section 20.5.1 and in Exercise 8.

    2. Exercise 21.1.{a,b,c}. Don't bother to formally prove your answers, but do explain your thinking.
      1. 21.1.a
      2. 21.1.b
      3. 21.1.c

    3. Dr. Okie's 115th Dream (with apologies). Answer the five questions (a .. e) below to explain your instructor's dream:

    4. After a nice meal of Thanksgiving leftovers, a thankful Dr. Okie falls asleep on the couch and dreams of his favorite course, ITEC 420. After telling a few stories and then lecturing for a few minutes he begins building Turing Machines. First he makes a working Universal Turing Machine (UTM). After some testing he's pumped because it all works just as expected. Carefully he explains to the class how his UTM is supposed to operate:

      1. In your own words in a sentence or two, describe the input to and output from the UTM.

      Now on a roll, he starts building MH, a decider for the language H. He tests it, and it works perfectly! (This is a dream, remember!?) Proud of his work he carefully explains MH:

      1. In your own words in a sentence or two, describe what strings MH accepts and what strings it rejects.

      Now, full of enthusiasm, he can't be stopped: he builds MT, to implement function Trouble. After complete and thorough testing, he decides that MT works perfectly, on every input string:

      1. IYOWIASOT, describe what a valid input for MT is and how MT operates on that input.

      But the excitement is too much and he awakes, ready to tell the class about the wonderful machines that he's built. But then he realizes that maybe MT doesn't work as well as he thought that it did. Sadly he reports the problem to the class:

      1. IYOWIASOT, describe what input string causes HUGE problems with MT, and why:

      Crushed, he doesn't understand what went wrong - his MT looked perfect. But by now, you are an expert on TM's, and you immediately see what's wrong. Letting him down gently you carefully explain the fatal flaw in his MT - the machine that looked perfect.

      1. IYOWIASOT, explain what is wrong with MT and what fundamental computer science result this illustrates.


Homework 10
  • Due Date: Friday 12/6/19, in class. Late assignments not accepted.
  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.
  • Some of the problems involve reduction which is discussed in the beginning of Chapter 21. (But note that overall Chapter 21 is much more involved than we need.) Some of the problems involve the language classes NP and NP Complete, which are covered in Chapter 28.

    1. You want to go have some fun by writing Turing Machines, but first you must write write a range routine for another class. Having just learned about problem reduction, you wonder, can I reduce range(nums: intArray) to some other routine, perhaps the routine sort(nums: intArray).

      Complete the routine range below to show that range reduces to sort (ie range ≤ sort).
    2.    type intArray is array(Positive range <>) of Integer;
      
         function range(nums: intArray) return Natural is ...
         -- Return distance between largest and smallest elements in nums
      
      
      
      
      
      
            return ...;
         end range;
      
      1. What can you say about the complexity (ie Big Oh) of your range routine.
      2. Is there a faster way to calculate range? What is it? How fast (Big Oh) is it?

    3. Now, even though you want to write some Turing Machines, you'd really like to do another reduction. Use the routine sort(nums: intArray) to make short work of the function isUnique(nums: intArray).

      Complete the routine isUnique below to show that isUnique reduces to sort. (ie isUnique ≤ sort).
    4.    function isUnique(nums: intArray) return boolean is
         --  Returns true if all elements of nums are unique 
         --    and false if nums contains duplicates 
            ans: Boolean := true;
         begin
      
      
      
      
            return ans;
         end isUnique;
      
      1. What can you say about the complexity (ie big Oh) of your isUnique as compared to the big Oh of sort?
      2. For class discussion: Are there faster algorithms for isUnique?

    5. You are having difficulty solving a problem (call it problem A). Eventually you successfully reduce the halting problem to problem A. What do you conclude about problem A? Justify your answer.

    6. Problem X is NP-Complete. You reduce problem X to some other problem in NP called problem Y. What can you conclude about problem Y?

    7. Problem X is NP-Complete. You find a polynomial time solution to problem X. What can you then conclude.

    8. What is the hard way to show that a problem X that is in NP is an NP-Complete problem?

    9. What is the (relatively) easy way to show that a problem X that is in NP is an NP-Complete problem?

No more homework!