Which one or more of the following types of automata can recognise all regular languages over the alphabet {a,b}?

Let  x  be a string, and let  M  be a Finite Automaton with just one Final State that accepts the strings  x  and  xx.

(a)   Prove, by induction on  n,  that  M  accepts the string  xⁿ  for every  n ≥ 1.

(b)   Would the same statement hold if  M  is a Nondeterministic Finite Automaton, also with just one Final State, instead?  Why or why not?

Write a regular expression for the language of all strings over the alphabet  {a,b}  in which every occurrence of the letter  a  has the letter  b  next to it on both left and right sides.

• variables  X  and  Y  can each represent any Nondeterministic Finite Automaton (NFA);
• the function  L(...)  returns the language recognised by the NFA given to it;
• the predicate   Deterministic(X)   is True if and only if  X  is actually also a Deterministic Finite Automaton (FA).

Let  P, Q, R  be the following propositions:

P:   My family name comes before my given name.

Q:   I am Chinese.

R:   I am Thai.

Using P, Q, R and appropriate connectives, construct a proposition in Conjunctive Normal Form to express the fact that my family name comes before my given name if I'm Chinese, while it comes after my given name if I'm Thai.

The following symbols are provided for you to copy if you wish (though not many of them are needed in this question, and you are not limited to using the symbols that are listed here):     ∃  ∀  ∧  ∨  ¬  ⇔  ⇒  ⇐  ∈  ≤  ≥  ≠

When doing a proof by induction, instead of showing that "if the statement is true for n, it is also true for n+1", we can appeal by saying that "we keep repeating the same process, or we do this over and over again...". 

Suppose we are tasked to prove that the sum of two positive integers, a and b, is also positive. We chose to use proof by contradiction. What is the first step?

To prove a statement by induction, the base case is always n = 1.