211L12Solutions

1. Let S be a k letter alphabet. Prove that for any given n, the number of strings over this alphabet of length n is equal to k^n.

For an alphabet of size 1, the number of ways a string of length n can be written is on. e.g. if the alphabet consists of 'a' the number of 6 letter strings which can be made from this is 1, "aaaaaa". For a two letter alphabet, again with the example of 6, there are 2x2x2x2x2x2 or 64 different possible combinations. For an alphabet with size k alphabet, the number of 6 letter strings is kxkxkxkxkxk or k^6. As such it is clear that changing 6 to 7 would give the number of 7 letter strings. The equation for any number length is thus k^n.

2. On the set �⋆ consider the following relations:

• (a) SubString = {(w, u) | w is a substring of u}.
• (b) Prefix = {(w, u) | w is a prefix of u}

Prove that SubString relation is reflexive and transitive. Prove that Prefix relation is reflexive, transitive and antisymmetric.

3. Let U, V and W be languages. Prove the following equality: U · (V ·W) = (U · V ) ·W.

• Let U = {aa}
• Let V = {bb)
• Let W = {aba}

By taking a string accepted by each language and concatenating in the from U · (V ·W) -> aa · (bbaba) -> aabbaba. This string is accepted by all three languages. (U · V ) ·W -> (aabb) · aba -> aabbaba, wich is the same as U · (V ·W).

4. Prove that U⋆∪V ⋆ ⊆ (U ∪V )⋆.Write down conditions of languages U and W that guarantee the equality U⋆ ∪ V ⋆ = (U ∪ V )⋆.

5. Let M be a DFA. Prove that the run of M on any given string w is unique.

6. Draw transition diagrams of DFA that recognize the following languages. The alphabet is always {a, b}.

• (a) {w1 | w ∈ �⋆}.
• (b) {�}.'
• (c) {w | w ∈ �⋆ and w 6= �}.
• (d) {uaabv | u, v ∈ �⋆}.

7. Construct the union and intersection automata for the following languages:

• (a) {uabv | u, v ∈ �⋆} and {ubbv | u, v ∈ �⋆}.
• (b) {u | the length of u equals 0 modulo 3} and {u | u contains even number of a}.

8. Prove that every finite language is DFA recognizable.

9. LetM1 andM2 be DFA recognizing languages L1 and L2, respectively. Give a formal proof that the DFA M1 ⊕M2, M1 ⊗M2, and M(c) 1 recognize the languages L1 ∪ L2, L1 ∩ L2, and �⋆ \ L2, respectively.

10. Draw transition diagrams for DFA recognizing the union and intersection of the languages {w | w ∈ {ab}⋆ and w w contains an odd number of a’s and an even number of b’s} and {aw | w ∈ {a, b}⋆}.

11. Let A be a DFA. Consider the DFA B obtained by removing all the states in A that are not reachiable from the initial state of A. Prove that A and B are equivalent.

12. Let A = (S, q0, T, F) and B = (S′, q0; , T ′, F′) be equivalent minimal DFA. Prove that there exists a function f : S → S′ that satisfies the following properties:

• (a) The function f is a bijection.
• (b) For any state s and symbol � ∈ �, f(T (s, �)) = T ′(f(s), �).

Comment: This exercise shows the equivalent minimal automata A and B are the same since one can be relabeled to get the other.