Login Registrieren

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: Q19E (page 1)

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

$a . (0 \cup 1) * 000 (0 \cup 1) * b . (((00) * (11)) \cup 01) * c . \emptyset *$

Short Answer

Expert verified

As per the above question the procedure for Lemma 1.55 use to convert regular expression to nondeterministic finite automata.

Step by step solution

01

To Convert Regular Expression

As per the above question, the procedure for Lemma 1.55 is used to convert regular expressions to nondeterministic finite automata. To, convert lemma 1.55 calculations is to follow, and count nondeterministic information is written below step-2 as below.

02

To the procedure described in Lemma 1.55 for regular expression

a. $(0 + 1) * 000 (0 + 1) *$

Consider the regular expression $R = (0 \cup 1) * 000 (0 \cup 1) *$ .

Now, construct an NFA from this regular expression in the following procedure:

The regular expression of 0

The regular expression of 1

The regular expression of $(0 \cup 1)$

The regular expression of $(0 \cup 1) *$

The regular expression of 000

The regular expression of $(0 \cup 1) * 000 (0 \cup 1) *$

03

To the procedure described in Lemma 1.55 for regular expression

$((00) * 11 + 01) *$

Consider the regular expression $R = (((00) * (11)) \cup (01)) *$ .

Now, construct the NFA from this regular expression in the following procedure:

The regular expression of 0

The regular expression of 1

The regular expression of 00

The regular expression of $(00) *$

The regular expression of 11

The regular expression of $(00) * 11$

The regular expression of 01

The regular expression of $(((00) * (11)) \cup (01))$

The regular expression of $(((00) * (11)) \cup (01)) *$

04

To the procedure described in Lemma 1.55 for regular expression

$\emptyset * = ε$

Let the normal expression $R = \emptyset *$ .

An unfilled format's closure is indeed an empty string. i.e., $\emptyset * = \{e\}$ . The NFA for the regular expression is as follows:

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

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 $\{0, 1\}$ . 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 .

Let

$\sum_{3} = \{[\begin{matrix} 0 \\ 0 \\ 0 \end{matrix}], [\begin{matrix} \begin{matrix} 0 \\ 0 \\ 1 \end{matrix} \end{matrix}], [\begin{matrix} \begin{matrix} 0 \\ 1 \\ 0 \end{matrix} \end{matrix}], - - - -, [\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}]\}$

$\sum_{3}$ contains all size 3 columns of 0s and 1 s. A string of symbols in $\sum_{3}$ gives three rows of 0s and 1s. Consider each row to be a binary number and let B= $\{W \in \sum_{} * 3\}$ the bottom row of W is the sum of the top two rows}.

For example,

$[\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}], [\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}], [\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}], [\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}] \in B b u t [\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}], [\begin{matrix} 1 \\ 0 \\ 1 \end{matrix}] \notin B$

Show that Bis regular.

(Hint: Working with $B^{R}$ is easier. You may assume the result claimed in Problem 1.31.)

A Turing machine with left reset is similar to an ordinary Turing machine, but the transition function has the form

δ : Q × Γ−→Q × Γ × {R, RESET}.

If δ(q, a) = (r, b, RESET), when the machine is in state q reading an a, the machine’s head jumps to the left-hand end of the tape after it writes b on the tape and enters state r. Note that these machines do not have the usual ability to move the head one symbol left. Show that Turing machines with left reset recognize the class of Turing-recognizable languages.

Consider the undirected graph $G = (V, E)$ where $V$ , the set of nodes, is ${1, 2, 3, 4}$
and $E$ , the set of edges, is ${{1, 2}, {2, 3}, {1, 3}, {2, 4}, {1, 4}} .$ Draw the graphG. What are the degrees of each node? Indicate a path from node 3 to node 4 on your drawing ofG.

Let F be the language of all strings over $\{0, 1\}$ that do not contain a pair of 1s that are separated by an odd number of symbols. Give the state diagram of a DFA with five states that recognizes $F$ . (You may find it helpful first to find a 4-state NFA for the complement of $F$ ).

See all solutions

Recommended explanations on Computer Science Textbooks

Issues in Computer Science

Read Explanation

Fintech

Read Explanation

Big Data

Read Explanation

Computer Systems

Read Explanation

Problem Solving Techniques

Read Explanation

Blockchain Technology

Read Explanation

View all explanations

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