Mock 3 – Finite Automata & Regular Languages (Part 3)

Ackermann's function is total recursive but not primitive recursive. aⁿbᵏcⁿ⁺ᵏ needs a stack, so it is context-free, not regular. {aⁿbʲ : n = j²} fails the CFL pumping lemma. Every CSL (without λ) is accepted by some LBA, so D is false.

The lemma requires |vx| ≥ 1, so at least one of v, x is non-empty; otherwise pumping would change nothing.

There is always exactly 1 initial state. Dead and unreachable states can be 0, and the language is non-empty, so at least 1 final state. At most n − 1 states can be dead or unreachable (the start state is neither), and all n can be final.

In every machine the start state is accepting and has a transition back to itself (or to accepting states) on both a and b, so every string over {a, b} can be read while staying in an accepting state. States that cannot be reached do not change the language, so all four accept {a, b}*.

LL starts with $S on the stack and w$ as input, and ends with $ and $. LR starts with $ and w$, and accepts with $S and $. (Item D's 'LL' should read LR.)

In xyz the pumped part y must be non-empty: |y| ≥ 1.

From q0 the ε-moves reach q2 without input; one a then reaches q3. Minimum length = 1.

∅ is the identity for union and the annihilator for concatenation; ε is the identity for concatenation. So a, b and c are correct and d is false.

Each a adds two 1's to the stack and each b removes one, so 2n b's are needed for n a's. The empty string is accepted directly from q0, so n ≥ 0.

Note on the official key: the official key says option A. Official/PW key is A ({a²ⁿbⁿ : n ≥ 0}). Each a pushes two 1's and each b pops one, so the machine needs twice as many b's as a's: {aⁿb²ⁿ}.

Each needs an unbounded counter to compare two quantities (n > k; matching the a's to n + k; n ≠ k), which a finite automaton cannot do. All three are non-regular.

Minimizing the given automaton (merging equivalent states and dropping unreachable ones) leaves 5 states, per the official key.

Following the official key, the language is (a + b)ab(ab + bb + aa*(a + b)ab)*: a first symbol, then ab to reach the accepting state, then any number of the loops that return to it.

q0 pushes the first half, nondeterministically switches to q1, then pops matching symbols in reverse order, accepting when the stack is back to z. That is the even-length palindromes wwᴿ.

(a* + b)* can produce any single a or b repeatedly, so it equals (a + b)* = all strings over {a, b}.

Even-length strings of a's, (aa)*, are regular. Perfect-square lengths and copies ww are not regular (pumping lemma).

Note: The exponents are garbled in the source; this reading (L2 = a^(2z)) is the one consistent with the official key.

r is every string starting with a; s is those of length at least 2; t (a⁺b) is a subset of those. So L(r) ⊇ L(s) ⊇ L(t).

t1 = i*j, t2 = e+f, t3 = a*b, t4 = t3+c, t5 = t2*t4, t6 = t1+t5: six quadruples.

States: start (loop on a), after b, and after one more symbol (accepting). That is 3 states, plus a dead state if the DFA must be complete.

Note: Counting the dead (trap) state as well gives 4.

s = a⁺b starts with a (so it is in r) and is a run of a's followed by b (so it is in t). But r contains 'a', which is not in s, so (ii) fails.

L has strings of length n, 2n, 3n, …, excluding ε. A cycle of n states counts length mod n, plus a separate start state so that ε is rejected: n + 1 states.

Regular languages are closed under 'first half' and 'first third' operations: run the DFA forward on x while guessing in parallel the states reachable by some suffix of length |x| (or 2|x|). Both are regular.

Two finite state machines are equivalent if they accept the same language (set of strings/tokens).

Horizontal a-edges flip a-parity and vertical b-edges flip b-parity. The start state is (even a, even b) and the accepting state, diagonally opposite, is (odd a, odd b).