Chapter 0: Q9E (page 27)
Write a formal description of the following graph.
The formal description of the graph is:
Over 30 million students worldwide already upgrade their learning with Vaia!
All the tools & learning materials you need for study success - in one app.
Get started for free
Which of the following pairs of numbers are relatively prime? Show the calculations that led to your conclusions
Consider the problem of determining whether a Turing machine M on an input w ever attempts to move its head left when its head is on the left-most tape cell. Formulate this problem as a language and show that it is undecidable.
Read the informal definition of the finite state transducer given in Exercise 1.24. Give the state diagram of an FST with the following behaviour. Its input and output alphabets are . Its output string is identical to the input string on the even positions but inverted on the odd positions. For example, on input 0000111 it should output 1010010 .
Myhill–Nerode theorem. Refer to Problem . Let L be a language and let X be a set of strings. Say that X is pairwise distinguishable by L if every two distinct strings in X are distinguishable by L. Define the index of L to be the maximum number of elements in any set that is pair wise distinguishable by L . The index of L may be finite or infinite.
a. Show that if L is recognized by a DFA with k states, L has index at most k.
b. Show that if the index of L is a finite number K , it is recognized by a DFA with k states.
c. Conclude that L is regular iff it has finite index. Moreover, its index is the size of the smallest DFA recognizing it.
Examine the following formal descriptions of sets so that you understand which members they contain. Write a short informal English description of each set.
What do you think about this solution?
We value your feedback to improve our textbook solutions.
