Theory of Computing > QUESTIONS & ANSWERS > California State University, San Marcos CS 421 Theory of computing CS421 - Yoshii - HW 2C (based  (All)

California State University, San Marcos CS 421 Theory of computing CS421 - Yoshii - HW 2C (based week 5-6) RE to DFA Automatic

Document Content and Description Below

California State University, San Marcos CS 421   Theory of computing  CS421 - Yoshii - HW 2C (based week 5-6) RE to DFA Automatic =============================================================... ======== DUE: Week 7 Friday before midnight TOTAL: 30 pts ** Name: **Qian Zhu Use my demo programs for these to verify your answers first!!! ------------------------------------------------------------------------------------- Problem 1: RE -> NFA-e (From week5a) [2pts per machine = 12 pts] ------------------------------------------------------------------------------------ Give NFA-e for the following REs. Show component machines first and then show all steps of connecting these machines using the methods described in week6a notes. Hand-drawing is OK (just insert into this file). [2pts per machine] Do not use any simplification. Having many e-moves is what we want. The following is for b(a|bb)^* No state numbers are needed for components.     HINT: Put M1 in front of M5 connected with a blank arrow and then give state numbers (make sure state numbers are unique) ------------------------------------------------------------------- Problem 2: NFA-e -> NFA (From week5b) [10 pts] --------------------------------------------------------------------- Remove e-moves from the following. I indicate e-moves with “e” on arrows.   i.e. the NFA is:   Trs(q8,e) = q9 final 1) Please compute Trs-e for each state-symbol pair: [6pts] Trs-e(q0, e* a e*) = { Trs-e(q0, e* b e*) = { Trs-e(q1, e* a e*) = { Trs-e(q1, e* b e*) = { Trs-e(q2, e* a e*) = { Trs-e(q2, e* b e*) = { nothing} etc. Continue for all state-symbol pairs.   2) Then draw the NFA based on the above results without simplification (hand-drawing is OK but insert here):[4pts]   ----------------------------------------------------------------------- Problem 3: NFA -> DFA (From week6a) [8 pts] ----------------------------------------------------------------------- Before we can implement a scanner, your machine has to become deterministic. NFA: q0 loop on 0,1 q2 loop on 0,1. q2 is final. (q0) --- 0 -----------> (q1) --- 1 ---> ((q2)) q1 loop on 0,1 Trs(q0, 0) = {q0, q1} Trs(q0, 1) = {q0} Trs(q1, 0) = {q1} Trs(q1, 1) = {q1, q2} Trs(q2, 0) = {q2} Trs(q2, 1) = {q2}   Then from each new resulting state, give Trs on 0 and 1 And finish this until there are no more new states. -- List all the Trs's here [4pts]   -- Then draw the resulting DFA showing all the Trs’s and mark all final states [2pts] :   B) What is the language accepted by this DFA? To answer, give its RE matching your DFA [2pts] :     [Show More]

Last updated: 1 year ago

Preview 1 out of 5 pages

Reviews( 0 )

Recommended For You

 Economics> QUESTIONS & ANSWERS > California State University, San Marcos - ECO 201ECO 201 & 202 Quizz (All)

preview
California State University, San Marcos - ECO 201ECO 201 & 202 Quizz

2. Individual and market demand Suppose that Sam and Teresa are the only consumers of pizza slices in a particular market. The following table shows their annual demand schedules: Price Sam's Quan...

By Kirsch , Uploaded: Apr 29, 2020

$14

 Biology> QUESTIONS & ANSWERS > California State University, San Marcos BIOLOGY 3 Biology 3.3.5 Adaptation and Natural Selection (All)

preview
California State University, San Marcos BIOLOGY 3 Biology 3.3.5 Adaptation and Natural Selection

3.3.5 Practice: Adaptation and Natural Selection Practice Assignment Florida Biology Sem 2 (S2974161) Christopher Bianco Points possible: 25 Date: ____________ 1. Draw a lake and label the photic,...

By d.occ , Uploaded: May 11, 2021

$7

 Psychology> QUESTIONS & ANSWERS > California State University, San Marcos PSYCHOLOGY PSYC 392Midterm_1_Questions (All)

preview
California State University, San Marcos PSYCHOLOGY PSYC 392Midterm_1_Questions

Which formal, mathematical approach to modeling perception uses conditional probabilities and prior probabilities to determine whether a hypothesis is true, given a certain set of observations? Ba...

By Cheryshev , Uploaded: Apr 27, 2021

$8

 Computer Science> QUESTIONS & ANSWERS > CMSC 303 Introduction to Theory of Computation, VCU Virginia Commonwealth University - CMSC 303CMSC303_Spring2017_A5_fullsolutions (All)

preview
CMSC 303 Introduction to Theory of Computation, VCU Virginia Commonwealth University - CMSC 303CMSC303_Spring2017_A5_fullsolutions

CMSC 303 Introduction to Theory of Computation, VCU Spring 2015, Assignment 5 Solutions Due: Thursday, March 30, 2017 in class Total marks: 38 marks + 4 marks bonus for typing your solutions in LaT...

By Expert Tutor , Uploaded: Apr 02, 2021

$7

 Mathematics> QUESTIONS & ANSWERS > California State University, San Marcos MATHEMATIC MATHEMATIC 441 Suppose that X is uniform on [-pi,2pi] . Find the probability density function of Y=sin(X). (All)

preview
California State University, San Marcos MATHEMATIC MATHEMATIC 441 Suppose that X is uniform on [-pi,2pi] . Find the probability density function of Y=sin(X).

Question Suppose that X is uniform on [-pi,2pi] . Find the probability density function of Y=sin(X).

By Muchiri , Uploaded: Mar 23, 2021

$5

 *NURSING> QUESTIONS & ANSWERS > Disproving the Theory of spontaneous Generation (All)

preview
Disproving the Theory of spontaneous Generation

The germ theory states that microorganisms are responsible for causing disease. This theory was initially not widely accepted; instead many people believed that this disease was caused by demons or wa...

By Senpai , Uploaded: Jan 27, 2021

$20

 Philosophy> QUESTIONS & ANSWERS > PHIL 2310 124 Theory of Ethics. Quiz 5. Graded A (All)

preview
PHIL 2310 124 Theory of Ethics. Quiz 5. Graded A

Quiz Question 1 (1 point) Saved The Greatest Happiness Principle is the idea that something is morally good when... Question 1 options: We disregard the consequences of our actions, focusin...

By Kirsch , Uploaded: Jan 06, 2020

$4.5

 Philosophy> QUESTIONS & ANSWERS > PHIL 2310 124 Theory of Ethics. Quiz 6. Graded A (All)

preview
PHIL 2310 124 Theory of Ethics. Quiz 6. Graded A

PHIL 2310 124 Theory of Ethics Quiz Submissions - Reading Quiz 6 The results of your quiz are shown here. You have 15 minutes to view them. Question 1 1 / 1 point What is "specesism", according...

By Kirsch , Uploaded: Jan 06, 2020

$5

 Microeconomics> QUESTIONS & ANSWERS > California State University, San Marcos ECON 201 Micro Economics  ECO 201 & 202 Quizz 4 (All)

preview
California State University, San Marcos ECON 201 Micro Economics  ECO 201 & 202 Quizz 4

2. Individual and market demand Suppose that Sam and Teresa are the only consumers of pizza slices in a particular market. The following table shows their annual demand schedules: Price Sam's Quant...

By Kirsch , Uploaded: Oct 05, 2022

$9

 Child Learning and Development> QUESTIONS & ANSWERS > Jean Piaget - Stage Theory of Development (All)

preview
Jean Piaget - Stage Theory of Development

Jean Piaget - Stage Theory of Development how does Jean Piaget's correlate, complement, or contradict the role of play in children? how may Jean Piaget's perspectives influence reading? Answer & E...

By destinyd , Uploaded: Feb 09, 2023

$7

$9.00

Add to cart

Instant download

Can't find what you want? Try our AI powered Search

OR

GET ASSIGNMENT HELP
65
0

Document information


Connected school, study & course



About the document


Uploaded On

Nov 15, 2022

Number of pages

5

Written in

Seller


seller-icon
Kirsch

Member since 4 years

898 Documents Sold


Additional information

This document has been written for:

Uploaded

Nov 15, 2022

Downloads

 0

Views

 65

Document Keyword Tags

THE BEST STUDY GUIDES

Avoid resits and achieve higher grades with the best study guides, textbook notes, and class notes written by your fellow students

custom preview

Avoid examination resits

Your fellow students know the appropriate material to use to deliver high quality content. With this great service and assistance from fellow students, you can become well prepared and avoid having to resits exams.

custom preview

Get the best grades

Your fellow student knows the best materials to research on and use. This guarantee you the best grades in your examination. Your fellow students use high quality materials, textbooks and notes to ensure high quality

custom preview

Earn from your notes

Get paid by selling your notes and study materials to other students. Earn alot of cash and help other students in study by providing them with appropriate and high quality study materials.

WHAT STUDENTS SAY ABOUT US


What is Browsegrades

In Browsegrades, a student can earn by offering help to other student. Students can help other students with materials by upploading their notes and earn money.

We are here to help

We're available through e-mail, Twitter, Facebook, and live chat.
 FAQ
 Questions? Leave a message!

Follow us on
 Twitter

Copyright © Browsegrades · High quality services·