Reference no: EM133234620

Consider a language L over the alphabet Σ = {a, b}. We say that L is finite if and only if there exists an integer k such that L contains at most k strings, i.e., |L| ≤ k. We say that L is infinite if and only if there is no such integer k.

a. Prove that if L contains exactly one word w, i.e., L = {w}, then L is a finite state language (i.e., that there exists a finite state automata that accepts L).

b. Prove that if L is a finite language, then L is also a finite state language.

c. Suppose that L is an infinite language. Prove that for any integer n, there exists a word w ∈ L such that |w| ≥ n, i.e., the length of w is at least n.