# A Classical Introduction to Cryptography Exercise BookElements of Complexity Theory

A Classical Introduction to Cryptography Exercise Book: Elements of Complexity Theory Chapter 8 Exercises Exercise 1 *Regular Language Describe the strings denoted by the regular language over the binary alphabet C = {0,1): . O(op)*l . (Oll>*l(Oll>(Oll) . 0*10* lo* lo* D Solution on page 177 Exercise 2 *Finite State Automaton Find the regular language over the binary alphabet C = {0,1) ac- cepted by the finite state automaton in Figure 8.1. D Solution on page 177 Exercise 3 *Turing Machine Of the class of recursively enumerable languages, there is an impor- tant subclass called recursive languages. A language L is defined to be recursive if there exists a Turing machine M that satisfies the following: EXERCISE BOOK The finite state automaton Figure 8.1. rn if the input w E L, then M eventually enters the halting state qXcept and accepts it; rn if w \$! L, then M eventually enters the halting state q,,jeCt and rejects it; the set F of all final states of M is defined to be F = {qaCcept). 1 Prove that a recursive language is recursively enumerable. 2 Prove that if L is a recursive language, so is its complement z. D Solution on page 177 Exercise 4 *Graph Colorability I Given an undirected http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

# A Classical Introduction to Cryptography Exercise BookElements of Complexity Theory

Springer Journals — Jan 1, 2006
4 pages

/lp/springer-journals/a-classical-introduction-to-cryptography-exercise-book-elements-of-SCGuzVfnWw
Publisher
Springer US
ISBN
978-0-387-27934-3
Pages
175 –179
DOI
10.1007/0-387-28835-X_8
Publisher site
See Chapter on Publisher Site

### Abstract

Chapter 8 Exercises Exercise 1 *Regular Language Describe the strings denoted by the regular language over the binary alphabet C = {0,1): . O(op)*l . (Oll>*l(Oll>(Oll) . 0*10* lo* lo* D Solution on page 177 Exercise 2 *Finite State Automaton Find the regular language over the binary alphabet C = {0,1) ac- cepted by the finite state automaton in Figure 8.1. D Solution on page 177 Exercise 3 *Turing Machine Of the class of recursively enumerable languages, there is an impor- tant subclass called recursive languages. A language L is defined to be recursive if there exists a Turing machine M that satisfies the following: EXERCISE BOOK The finite state automaton Figure 8.1. rn if the input w E L, then M eventually enters the halting state qXcept and accepts it; rn if w \$! L, then M eventually enters the halting state q,,jeCt and rejects it; the set F of all final states of M is defined to be F = {qaCcept). 1 Prove that a recursive language is recursively enumerable. 2 Prove that if L is a recursive language, so is its complement z. D Solution on page 177 Exercise 4 *Graph Colorability I Given an undirected

Published: Jan 1, 2006

Keywords: Turing Machine; Complexity Theory; Polynomial Time Algorithm; Graph Colorability; Regular Language