CS 241 Final Review Questions w/ Solutions (1)

Reference: https://www.student.cs.uwaterloo.ca/~cs241/final/CS241_Winter_2019_Final_Review.pdf

True of False

  1. For any MIPS assembly program, the number of entries in its symbol table is always less than or equal to the number of instructions.

    • False. The number of entries in the symbol table is the number of labels defined. Since
      you can define more than one labels for one line of instructions, the number of symbol
      table entries can be more than the number of instructions.
  2. The largest positive decimal value that can be expressed by a $k$-bit two’s complement number is $2^{k-1}$.

    • False. Since the first bit is a sign bit, you have $k-1$ bits to represent a number. The number of possible numbers you can represent is $2^{k-1}$. Since $0$ is counted as one of the possibilities. The largest possible number is $2^{k-1}-1$.
  3. For any language $A$, if there exists an NFA $M$ such that $L(M) = A$, then there exist a CFG
    $G$ such that $L(G)=A$.

    • True. An NFA language is a DFA language. A DFA language is a regular language. Since CFG languages are supersets of regular languages, there exists such a CFG $G$ such that $L(G)=A$.
  1. If any language $C$ is regular, then $\overline C$ is also regular.
    • True.
    • $C = L(M_0)$ where $M_0 = (\Sigma, \delta, Q, q_0, A)$
    • $C = L(M_1)$ where $M_1 = (\Sigma, \delta, Q, q_0, Q/A)$
    • Remark: We can construct a DFA to represent a regular language. For every non-accepting state of the DFA, we change it to an accepting state. For every accepting state of the DFA, we change it to a non-accepting state. Then, the changed DFA represents $\overline C$. Since the changed DFA is a valid DFA, $\overline C$ is a regular language.

Regular Expression to DFA

Given a regular expression for the following language: The string over $\Sigma = \{a,b\}$ such that no two consecutive letters are the same.

Context Free Grammar

  1. $\star$Give an example of a language that is context-free, but not regular.
    • $L = \{ 0^n 1^n : n\in \mathbb N \}$
    • $L$ is context-free, and can be recognized by the grammar: $$S \to 0 S 1 | \epsilon$$
    • $L$ is not regular. Assume $L$ is regular. Then, $L$ can be recognized by some DFA. Since the DFA needs somehow keep track of how many $0$’s and $1$’s have been read, such as $$<\#\text{ of }0=0, \#\text{ of }1=0>,<\#\text{ of }0=1, \#\text{ of }1=1>,<\#\text{ of }0=2, \#\text{ of }1=2>,\dots$$
    • We can conclude that the number of state must be infinite. Since the state set of a DFA is finite, this is a contradiction.
    • $L$ is a language that is context-free, but not regular.
  1. What does it mean for a context-free grammar to be ambiguous? Give an example of an ambiguous context-free grammar.
    • You have two parse trees for the same word.
    • Consider the grammar: $S\to A+A$, $A\to A+A$, and $A\to a$.
    • Let $w = a+a+a$. We show that there are two parse trees for $w$.
    • Hence, this CFG is ambiguous.
  1. Perform both a leftmost and rightmost derivation on the string $aaabbc$ given the grammar specified by the following rules:

    • Grammar rule:

      S -> aABc
      A -> aA
      A ->
      B -> bb
    • Leftmost derivation:

      S => aABc => aaABc => aaaABc => aaaBc => aaabbc
    • Rightmost derivation:

      S => aABc => aAbbc => aaAbbc => aaaAbbc => aaabbc

Top Down Parsing

  1. What does $LL(1)$ parsing stands for? When is a grammar not $LL(1)$?

    • $LL(1)$ stands for
      • “L” - left-to-right
      • “L” - left-canonical
      • “1” - with one look-ahead
    • Any entry of the predictor table has more than one entry.
  2. Build a predictor table for the following grammar, then parse the string |- deaccb -|.

    • Grammar:

      S' -> |- S -|   (0)
      S -> aYb (1)
      S -> XS (2)
      Y -> ccY (3)
      Y -> (4)
      X -> de (5)
    • To build a predictor table, we first need to build a nullable-first-follow table.

    • Nullable:

      S'  F
      S F
      Y T
      X F
    • First:

      S'  {|-}
      S {a, d}
      Y {c}
      X {d}
    • Follow:

      S'  {}
      S {-|}
      Y {b}
      X {a, d}
    • Predictor Table:
      Look at the rules to fill in the table.

    • $\star$Use the predictor take to parse the string |- deaccb -|.

      Reference: https://cs.uwaterloo.ca/~cbruni/CS241Resources/lectures/2019_Winter/CS241L11_parsing_post.pdf

      1. Stack is empty at the beginning.
      2. Push [S’] onto the stack.
      3. Whenever the stack is non-empty, pop the stack.
        1. If the item is a non-terminal symbol, push the RHS of the correct derivation in reverse order onto stack.
        2. If the item is a terminal symbol, compare it with the next character.
          1. If different, reject.
          2. Otherwise, continue.
      4. Only when we have run out of characters, accept the string lastly.