4P61 Cheat Sheet: Automata and Formal Languages

Posted on Jan 13, 2025 in Computational Mathematics

4P61 Cheat Sheet

Assignment 1

1) Function f: N→N has a fixed point at i such that f(i) = i. Show that the set is not countable.

Answer: If countable, f₁, f₂,… define function f; f(i) = f_i(i) + i for i = 1, 2, 3,…

Therefore, (1) f does not have a fixed point since f(i) > i and (2) f ≠ f_i since f(i) ≠ f_i(i); i.e., not countable.

2) k≥1, A: N→(1, 2,… k), B: (1, 2,… k)→N. Is A or B countable?

Answer: k=1, only 1 function. If A is finite, then yes, it is countable. k>1, similar to the proof in class, then the set of binary functions is uncountable. Assume countable, let f₁, f₂,… be functions; define a new function: f(i)=f_i(i)+1 if f_i(i)<k, f(i)=1 if f_i(i)=k.

3) Proper subset – B is a proper subset of A means all elements in B are in A, but A has at least 1 element not in B. Converse: if q→p.

4) Onto but not 1-1: 2i-2, i>2; 1-1: 2i.

5) a) An infinite countable set that is a subset of (0,1): (1/2, 1/4, 1/8,…). (a,b) for any 0<a<b<1 – an uncountable set that is a proper subset of (0,1).

10) x011=011x where xε(0,1)*: x>1

Assignment 2

• If you see δ(q₀,a)={q₁,q₂}, it means 2 different states (q₁) and (q₂). [q₁,q₂] means one state.
• 3) L1 = a* (regular), L2 = (a^p|p is prime), L1υL2 (regular).
• b) L1 = a² (regular), L2=(aⁿbⁿ|n≥1) (nonregular), L1υL2 (nonregular).
• c) L1=a² (regular), L2=(aⁿbⁿ|n≥1), L1∩L2 (regular).
• d) Any nonregular language and its complement gives you L* (regular) (L1υL2).
• 5b) a^pa^q|q is a prime, p is not a prime. Use the pumping lemma; every even number 2k≥6 is a sum of a prime and a composite number, 2k = 2+2(k-1), 2 is a prime and 2(k-1) is composite because k≥3. Every odd number 2k+1 ≥7 is a sum of a prime and a composite number. The regular expression is aaaaaa⁺, a string of at least 6 a‘s.

Other Tips

• If |x| = m, then |2^x| = 2^m i.e., the power set.
• Distributive property: X∩(YυZ) = (X∩Y)υ(X∩Z).
• Onto – every element in the set is used.
• 1-1→every element in set A is used and points to only one element in set B.
• Bijection – both onto and 1-1.
• If X and Y are both infinite, |X| = |Y| iff at least 1 (1-1) between X and Y.
• The union of countable sets is also countable.
• Can enumerate by mapping functions.
• (0,1), numbers between 0 and 1 is not countable→can show using the technique of diagonalization.
• A finite set is always countable.
• Technique of Diagonalization:
  • First, make a new function (f) that follows other functions.
  • Put the elements in diagonal from the table of functions into your new function. The new function should be in the list; if not, then it is not countable.
  • Always assume countable first for the technique of diagonalization.
• Cantor – for any set A, |A| < |2^A|; if |A| = n (finite), then |2^A| = 2ⁿ.
• Prefix – any number of leading symbols.
• Suffix – any number of trailing symbols.
• Concatenation of strings – xy, order matters- xy≠yx.
• Kleene closure→ L* includes the empty string as well.
• Positive closure → L⁺ same as Kleene, does not include the empty string.
• DFA – M=(Q,∑,δ,q₀,F), Q-finite set of states, Σ is the alphabet, q₀ is the initial state, F is the final states, δ is the transition function.
• From NFA to DFA, there are 2^Q states in the DFA, Q are the number of states in the NFA.
• The theorem states that if L is accepted by NFA, then there is also a DFA and NFA without E moves. NFA = DFA = NFA without E moves.
• Can show a language is regular by doing one of 4 things: regular expression, NFA, DFA, or NFA without E Moves.
• If L is finite, then L is regular for sure.
• Example: s mod 3→only 3 possible values, 0, 1, 2.

Adding 0 is the same as x2, adding 1 is the same as x2+1. Give 0 state a 0 goes to 0 state, give 0 state a 1, goes to state 1, give state 1 a 0 goes to state 2, and so on.

• MyHill-Nerode theorem – any finite language is regular, any nonregular language is infinite.
• Pumping lemma – necessary condition for a language to be regular. There exists n such that zεL, |z| ≥n, z = uvw where |uv| ≤n, |v| ≥ 1 such that for any i≥0, uvⁱwεL.

Midterm

3a) (00)⁺.

• ((ba)*ba)* is really (ba)⁺.
• If set A has a proper subset that is uncountable, then A is uncountable.
• Example: a^j| j is prime, show nonregular. a) z=a^p, p is prime, p≥n. z=uvw=a^ua^va^w, want uvⁱw not in L, want to find the i. Want to find u+vi+w is no longer a prime. = u+v+w+(i-1)v =p+(i-1)v, i = p+1→p is prime so prime +1 makes it composite, i.e., not in L.