/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Q1E Question: Answer all parts for t... [FREE SOLUTION] | 91影视

91影视

Log out

Learning Materials

Features

Discover

Chapter 0: Q1E (page 1)

Question: Answer all parts for the following DFA and give reasons for your answers.

a.Is<M,0100>鈭�ADFA?b. Is<M,011>鈭�ADFA?c. Is<M>鈭�ADFA?d. Is<M,0100>鈭�AREX?e. Is<M>鈭�EDFA?f. Is<M,M>鈭�EQDFA?

Short Answer

Expert verified

Answer

  1. Yes
  2. No
  3. No
  4. No
  5. No
  6. Yes

Step by step solution

01

Explain Deterministic Finite Automata 

A Deterministic Finite Automata is the computational model that determines the state of the input symbol provided.

02

Step 2: Is  <M,0100>∈ADFA

a.

Consider the given diagram, assume that the states are named as follows,

M,0100, represents the inputs of the machine. Symbol 0 starts with the state S , the next input 1 takes to the state A . The input symbol 0 moves to the state B and the next input 0 is the last symbol of the string that ends in the state S ,which accepts the input.

Therefore, Yes, M,0100鈭�ADFA.

03

Step 3: Is  M,011∈ADFA

b.

Consider the given diagram, assume that the states are named as follows,

M,011, represents the inputs of the machine. Symbol 0 starts with the state S , the next input 1 takes to the state A . The input symbol 0 is the last symbol of the string that ends in the state B ,which doesnot accepts the input.

Therefore, No, M,011鈭�ADFA.

04

Step 4: Is <M>∈ADFA

c.

Consider the given diagram, assume that the states are named as follows,

M, represents the inputs of the machine. The input symbol empty is not accepted by the given automata.

Therefore, No,role="math" M鈭�ADFA .

05

Step 5: Is  <M,0100>∈AREX

d.

Consider the given diagram, assume that the states are named as follows,

M,0100, represents the inputs of the machine. The input symbol is belongs to DFA not the regular language inputs.

Therefore, No,M,0100鈭�AREX

06

Step 6: Is  <M>∈EDFA

e.

Consider the given diagram, assume that the states are named as follows,

M, represents the empty input of the machine. The input symbol is belongs to DFA not the regular language inputs.

Therefore, No,M鈭�EDFA.

07

Step 7: Is  <M,M>∈EQDFA

e.

Consider the given diagram, assume that the states are named as follows,

M,M, represents the same language of the machine. The input symbol belongs to the DFA.

Therefore, Yes,M,M鈭�EQDFA.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with 91影视!

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

Examine the following formal descriptions of sets so that you understand which members they contain. Write a short informal English description of each set.

  1. {1,3,5,7,...}
  2. {...,-4,-2,0,2,4,...}
  3. {n|n=2mfor someminN}
  4. {n|n=2mfor someminN, andn=3kfor somekinN}
  5. {w|wis a string of0sand1sandwequals the reverse ofw}
  6. {n|nis an integer andn=n+1}

Question: Describe the error in the following 鈥減roof鈥� that 0*1*is not a regular language. (An error must exist because 0*1*is regular.) The proof is by contradiction. Assume that 0*1*is regular. Let p be the pumping length for localid="1662103472623" 0*1*given by the pumping lemma. Choose s to be the string 0p1p . You know that s is a member of 0*1*, but Example 1.73 shows that s cannot be pumped. Thus you have a contradiction. So 0*1* is not regular.

Let X=M,wM is a single-tape TM that never modifies the portion of the tape that contains the input w. Is X decidable? Prove your answer.

Give a counterexample to show that the following construction fails to prove Theorem 1.49, the closure of the class of regular languages under the star operationLet N1=Q1,危,未1,q1,F1 recognize . Construct N=Q1,危,未,q1,F as follows. Nis supposed to recognize A*1.

a. The states of Nare the states of N1.

b. The start state ofN is the same as the start state ofN1 .

c. . F=q1鈭�F1.The accept states are the old accept states plus its start state.

d. Define未so that for any and any a鈭�危蔚, 未q,a=(未1q,aq6鈭�F1ora6=蔚未1q,a鈭�q1q鈭�F1anda=蔚

Use the recursion theorem to give an alternative proof of Rice鈥檚 theorem in Problem 5.28.
See all solutions

Recommended explanations on Computer Science Textbooks

Computer Systems

Read Explanation

Big Data

Read Explanation

Data Representation in Computer Science

Read Explanation

Computer Organisation and Architecture

Read Explanation

Problem Solving Techniques

Read Explanation

Databases

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.