## CS 3350 Automata, Computability, and Formal Languages Fall 2012 Final Exam

Name: __________________________________________________________

1 (8 points). Prove that the square root of 6 is irrational.

```

```
2 (16 points).

2a. Use a general algorithm to design a non-deterministic finite automaton recognizing the following language:

0*U 01*
(Here, AB means concatenation of two languages A and B.)

2b. Apply the general algorithm to transform the non-deterministic finite automaton from Part 2a a deterministic finite automaton recognizing this same language.

```

```
3 (16 points).

3a. Use a general algorithm to transform the following finite automaton (for checking whether a given binary number is even) into the corresponding regular expression. This automaton recognizes signed binary integers. The alphabet for this automaton consists of symbols 0, and 1. The automaton has three states:

• the starting state s0,
• the state r0 meaning that we have just read 0,
• the state r1 meaning that we have just read 1.
The transition is as follows:
• when we see 0, we move to r0;
• when we see 1, we move to r1.
The state r0 is the only final state.

3b. On the example of this automaton, explain, in detail, how the following sequences will be presented as xyz according to the pumping lemma: 00 and 110. For each of these sequences, check -- by tracing step-by-step -- that the sequences xyiz for i = 2 are indeed accepted by the automaton.

```

```
4 (8 points). Use Pumping Lemma to prove that the language L consisting of all the words that have at least three times as many b's as a's is not regular. This language includes an empty string ε, strings abbb, bbba, babbb, bbbaabbbb, etc.

```

```
5 (24 points).

5a. Use the algorithm that we had in class to transform the following context-free grammar into Chomsky normal form: S --> AA, A --> BaB, B --> AbA, A --> ε, B --> ε.

5b. Use the general algorithm to design a pushdown automaton that recognizes exactly the above context-free language.

5c. For the above context-free grammar:

• draw a tree that describes the derivation of the sequence bab,
• use this tree to determine the subdivision of this sequence into u, v, x, y, and z;
• for i = 0 and i = 2, draw trees explaining how the corresponding sequences uvixyiz can be derived in this grammar.

```

```
```

```
```

```
6 (8 points) The sequence babb is accepted by the following non-deterministic pushdown automaton:
• this automaton starts at state 0,
• when in state 0, the rule (b, ε) --> a leads to state 1,
• when in state 1, the rule (a, a) --> b leads to state 2,
• when in state 2, the rule (b, ε) --> t leads to state 2 again,
• when in state 2, the rule (ε, t) --> ε leads to state 3,
• when in state 3, the rule (b, b) --> ε leads to the state 1, which is a final state.
Use the general algorithm that we described in class (and that is described in the book) to list all the rules of the corresponding context-free grammar which are needed to deduce the sequence babb. Draw a parse tree explaining how this sequence is derived by using these rules.

```

```
7 (8 points). Let Na(s) denote the number of a's in a string s, Nb(s) denote the number of b's, and Nc(s) denote the number of c's. Prove that the language consisting of all the words s for which Na(s) >= 3 * Nb(s) and Na(s) >= 3 * Nc(s) (i.e., words which have exactly at least three times as many a's as b's or c's) cannot be recognized by a pushdown automaton.

```

```
8 (16 points).

8a. Design a Turing machine for making a given word plural:

• if the given word ends in s or in z, we add "es"
• in all other cases, we add "s".
Trace it step-by-step on the example of a string "Oz".

8b. Formula Church-Turing thesis. It is a mathematical theorem? Can it be proven? Is it a statement about the physical world?

```

```
9 (8 points). Let us assume that we have the following sequence of real numbers:
• x1 = 0.0666...
• x2 = 0.1300...
• x3 = 0.2012...
• ...
Use the diagonalization algorithm that we described in class to generate the first three digits of a real number y that does not belong to this sequence.