LMU ☀️ CMSI 3802
LANGUAGES AND AUTOMATA II
HOMEWORK #4 Due: 2025-04-22

Learning Objectives

In this assignment you will demonstrate:

Readings, Videos, and Self-Study

Although your team will be turning in only one submission, every team member is individually responsible for each of the following:

Submission Instructions

As usual, turn in a single submission for your entire group via BrightSpace. Remember to not simply partition the work among team members, as this reduces your learning.

Your team's BrightSpace submission should be an attached PDF or text file with:

Exercises

  1. In your own words, write one sentence for each of the four major theories of computation, conveying its central question and its areas of concern. Write as if your job depended on clarity, accuracy, and solid English writing skills. If you look to an AI assistant for help, do not just copy what the bot says; but feel free to try so see if it can even get close on this one. The scope of the four theories are kind of fuzzy, so stick with the definitions you’ve heard in class rather than the bot’s training set.
  2. Given $L_1 = \{0, 011, 10\}$ and $L_2 = \{10, 1\}$. What are:
    1. $L_1 \cup L_2$
    2. $L_1 \cap L_2$
    3. $L_1L_2$
    4. ${L_2}^*$
  3. Give grammars for the following languages (using the notation from class):
    1. The empty language
    2. $\{ 0^i1^j2^k \mid i=j \vee j=k \}$
    3. $\{ w \in \{0,1\}^* \mid w \textrm{ does not contain the substring 000} \}$
    4. $\{ w \in \{a,b\}^* \mid w \textrm{ has twice as many $a$'s as $b$'s} \}$
    5. $\{ a^nb^na^nb^n \mid n \geq 0 \}$
    (Note that not all of these are expressible with Ohm.)
  4. Here’s another look at the grammar for floating-point numerals (using single-letter variables for compactness):

    $\begin{array}{l} n \longrightarrow d^+ \; f? \; e? \\ f \longrightarrow \texttt{"."} \; d^+ \\ e \longrightarrow (\texttt{"E"} | \texttt{"e"})\; (\texttt{"+"} | \texttt{"–"})? \; d^+ \\ d \longrightarrow \texttt{"0"} .. \texttt{"9"} \\ \end{array}$

    Give the $(V, \Sigma, R, S)$-definition of this grammar. (Note this means you will have to desugar the rules with |, ?, and +.)
  5. Give Turing Machines that recognize the following languages. If any of the languages below are Type-3, you may (and are encouraged to) give a FA in lieu of a TM recognizer, if the FA is simpler.
    1. $\{w \in \{a,b\}* \mid w \textrm{ ends with } abb\}$
    2. $\{ w \in \{a,b\}^* \mid \#_a(w) = \#_b(w) \}$ (same number of $a$'s as $b$'s)
    3. $\{w \in \{a,b\}* \mid w \textrm{ alternates } a\textrm{'s and } b\textrm{'s} \}$
    4. $\{ a^nb^na^nb^n \mid n \geq 0 \}$
  6. Give Turing Machines that compute the following functions, where the input and output are binary numerals.
    1. $\lambda n. 2n + 2$
    2. one's complement
    3. The function described in Python as lambda n: str(n)[1:-1]
  7. For the JavaScript/Python expression 5 * 3 - 1 ** 3,
    1. Show a 3AC machine program to evaluate this expression, leaving the result in $r_0$
    2. Show a Stack machine program to evaluate this expression, leaving the result on the top of the stack.
  8. Characterize each of the following languages as either (a) regular, (b) context-free but not regular, (c) recursive but not context-free, (d) recursively enumerable but not recursive, or (e) not even recursively enumerable.
    1. $\{ a^ib^jc^k \mid i > j > k \}$
    2. $\{ a^ib^jc^k \mid i > j \wedge k \leq i-j \}$
    3. $\{ \langle M\rangle\cdot w \mid M \textrm{ accepts } w\}$
    4. $\{ G \mid G \textrm{ is context-free} \wedge L(G)=\varnothing \}$
    5. $\{ a,b \}^*\{b\}^+$
    6. $\{ \langle M\rangle \mid M \textrm{ does not halt }\}$
    7. $\{ w \mid w \textrm{ is a decimal numeral divisible by 7} \}$
    8. $\{ www \mid w \textrm{ is a string over the Unicode alphabet} \}$

For Your Project

Continue your compiler project in the public GitHub repository you created in the first assignment. You will be expanding your repo to have the following:

  .
  ├── .gitignore
  ├── README.md
  ├── LICENSE
  ├── package.json
  ├── .prettierrc.json
  ├── docs
  │   └── ...
  ├── examples
  │   └── ...
  ├── src
  │   ├── (yourlanguagename).js
  │   ├── (yourlanguagename).ohm
  │   ├── compiler.js
  │   ├── core.js
  │   ├── analyzer.js
  │   ├── optimizer.js        -- updated as below
  │   └── generator.js        -- flesh this out!
  └── test
      ├── compiler.test.js
      ├── grammar.test.js
      ├── analyzer.test.js
      └── generator.test.js    -- new!

In this assignment you will be completing the following tasks:

Grading Rubric

To help you get a good score, here are all the things you will be graded on.

Make sure to make all corrections on your project and project companion site from the previous assignments.