Open In App

Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Introduction to Theory of Computation

Michael Sipser

Computer Science

3rd Edition · 458 pages

ISBN: 9781133187790

Chapter 0: Q19P (page 1)

In the silly Post Correspondence Problem, SPCP, the top string in each pair has the same length as the bottom string. Show that the SPCP is decidable.

Short Answer

Expert verified

It is proved that Silly Post Correspondence Problem (SPCP) is decidable.

Step by step solution

Decidability

A problem is decidable if there Turing Machine exist which will halt in finite amount of time.

Proving SPCP is decidable

Now as the each pairs have equal length at top and at bottom string, so it means total length of string at top and at bottom are equal.

Thus if we construct a Turing Machine, there is only one way by which our TM will be decidable i.e., if top and bottom in the pair are the same.

Let us construct a Turning Machine M such that

M = for each pair

Check if TOP and BOTTOM are equal

·If EQUAL, then check the next pair

If NOT EQUAL, Reject M .

If all the pairs are resolved, Accept M .

Thus, SPCP is decidable.

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Consider the language B=L(G), where Gis the grammar given in

Exercise 2.13. The pumping lemma for context-free languages, Theorem 2.34,

states the existence of a pumping length p for B . What is the minimum value

of p that works in the pumping lemma? Justify your answer.

Show that the function K(x) is not a computable function.

Question:Consider the algorithm MINIMIZE, which takes a DFA as input and outputs DFA .

MINIMIZE = “On input , where $M= (Q, Σ, δ, q 0, A)$ is a DFA:

1.Remove all states of G that are unreachable from the start state.

2. Construct the following undirected graph G whose nodes are the states of .

3. Place an edge in G connecting every accept state with every non accept state. Add additional edges as follows.

4. Repeat until no new edges are added to G :

5. For every pair of distinct states q and r of and every $a \in Σ$ :

6. Add the edge (q,r) to G if $(δ (q, a), δ (r, a))$ is an edge of G .

7. For each state $q, let [q]$ be the collection of $states [q] = {r \in Q | no$ edge joins q and r in G }.

8.Form a new DFA $M' = (Q', Σ, δ', q'_{0}, A')$ where

$Q'={[q] | q \in Q} (i f [q] = [r], o n l y o n e o f t h e m i s i n Q'), δ' ([q], a) = [δ (q, a)] f o r e v e r y q \in Q a n d a \in Σ, q 00 = [q 0], a n d A 0 = {[q] | q \in A}$

9. Output ( M^')”

a. Show that M and M^' are equivalent.

b. Show that M0 is minimal—that is, no DFA with fewer states recognizes the same language. You may use the result of Problem 1.52 without proof.

c. Show that MINIMIZE operates in polynomial time.

Use the procedure described in Lemma 1.60 to convert the following finite automata to regular expressions.

Let $P = \{a, b\} .$ Give a CFG generating the language of strings with twice as many $a' s a s b' s$ . Prove that your grammar is correct.

See all solutions

Recommended explanations on Computer Science Textbooks

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free

In the silly Post Correspondence Problem, SPCP, the top string in each pair has the same length as the bottom string. Show that the SPCP is decidable.

Short Answer

Step by step solution

Decidability

Proving SPCP is decidable

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Computer Science Textbooks

Data Structures

Game Design in Computer Science

Fintech

Problem Solving Techniques

Computer Programming

Functional Programming

Study anywhere. Anytime. Across all devices.

Company

Product

Help