new trans nfa qs Type ( ' q , ' s ) nfa t ' q list ( ' q list, ' s ) transition list Description The inputs are an NFA and a list of states The output is a transition list Each element in the returned list is a tuple in the form of ( src , char, dest ) , where dest is the list of states you can get to after starting from any state in the inputted list and moving on one character of the alphabet ( sigma ) , followed by any number of epsilon transitions This may seem a little confusing at first, so make sure you look at the examples below Examples type ( ' q , ' s ) transi ' q ' s option ' q type ( ' q , ' s ) nfa y sigma ' s list qs ' q list q 0 ' q fs ' q list delta ( ' q , ' s ) transi list let nfa 2 sigma ' z ' qs 1 2 3 q 0 1 fs 3 delta ( 1 , Some ' z ' , 2 ) ( 2 , None, 3 ) let dfa 2 sigma ' z ' ' y ' ' x ' qs 1 2 3 q 0 1 fs 3 delta ( 1 , Some ' z ' , 2 ) ( 2 , Some ' y ' , 1 ) ( 2 , Some ' x ' , 3 ) transFresh nfa 2 1 ( 1 , Some ' z ' , 2 3 ) transFresh dfa 2 1 2 ( 1 2 , Some ' z ' , 2 ) ( 1 2 , Some ' y ' , 1 ) ( 1 2 , Some ' x ' , 3 ) transFresh dfa 2 2 3 ( 2 3 , Some ' z ' , ) ( 2 3 , Some ' y ' , 1 ) ( 2 3 , Some ' x ' , 3 ) Explanation Starting from state 1 in nfa 2 , we can move only to state 2 on ' z ' and then from state 2 to state 3 on epsilon, which gives us the tuple ( 1 , Some ' z ' , 2 3 ) ' z ' is the only character in the alphabet So , we return ( 1 , Some ' z ' , 2 3 ) Starting from either state 1 or state 2 in dfa 2 , we want to see where we can move to If we start at 1 , we can move to 2 on ' z ' , and if we start at 2 , there isn't an ' z ' transition There are no states we can move to from 2 via epsilons ( because it's a DFA ) , so we have the tuple ( 1 2 , Some ' z ' , 2 ) Then, starting again from either state 1 or state 2 , we can move to 1 on ' y ' from 2 , and there isn't a ' y ' transition from 1 to another state There are no states we can move to from 1 via epsilons, so we have the tuple ( 1 2 , Some ' y ' , 1 ) Then, starting again from either state 1 or state 2 , we can move to 3 on ' x ' from 2 , and there isn't a ' x ' transition from 1 to another state There are no states we can move to from 3 via epsilons, so we have the tuple ( 1 2 , Some ' x ' , 3 ) So , our overall returned list is ( 1 2 , Some ' z ' , 2 ) ( 1 2 , Some ' y ' , 1 ) ( 1 2 , Some ' x ' , 3 ) Starting from either state 2 or state 3 in dfa 2 , there is no ' z ' transition that starts from either state 2 or state 3 So , we have ( 2 3 , Some ' z ' , ) Then, starting again from either state 2 or state 3 , we can move to 1 on ' y ' from 2 , and there isn't a ' y ' transition from 3 to another state There are no states we can move to from 1 via epsilons ( because it's a DFA ) , so we have ( 2 3 , Some ' y ' , 1 ) Then, starting again from either state 2 or state 3 , we can move to state 3 on ' x ' from 2 , and there isn't a ' x ' transition from 3 to another state There are no states we can move to from 3 via epsilons, so we have ( 2 3 , Some ' x ' , 3 ) So , our overall returned list is ( 2 3 , Some ' z ' , ) ( 2 3 , Some ' y ' , 1 ) ( 2 3 , Some ' x ' , 3 )

The Answer is in the image, click to view ...

Question: new _ trans nfa qs Type: ( ' q , ' s ) nfa _ t - > ' q list - > ( '

new

_

trans nfa qs

Type:

('

,'

)

nfa

_

- >'

q list

- > ('

q list,

'

)

transition list

Description: The inputs are an NFA and a list of states. The output is a transition list. Each element in the returned list is a tuple in the form of

(

src

,

char, dest

),

where dest is the list of states you can get to after starting from any state in the inputted list and moving on one character of the alphabet

(

sigma

),

followed by any number of epsilon transitions. This may seem a little confusing at first, so make sure you look at the examples below!

Examples:

type

('

,'

)

transi

='

*'

s option

*'

type

('

,'

)

nfa

_

= {

sigma :

'

s list; qs :

'

q list; q

0

'

q; fs :

'

q list; delta :

('

,'

)

transi list;

}

let nfa

2 = {

sigma

= ['

']

; qs

= [1

;

2

;

3]

; q

0 = 1

; fs

= [3]

; delta

= [(1,

Some

'

', 2)

;

(2,

None,

3)]}

let dfa

2 = {

sigma

= ['

'

;

'

'

;

'

']

; qs

= [1

;

2

;

3]

; q

0 = 1

; fs

= [3]

; delta

= [(1,

Some

'

', 2)

;

(2,

Some

'

', 1)

;

(2,

Some

'

', 3)]}

;;

transFresh nfa

2 [1] = [([1],

Some

'

', [2

;

3])]

transFresh dfa

2 [1

;

2] = [([1

;

2],

Some

'

', [2])

;

([1

;

2],

Some

'

', [1])

;

([1

;

2],

Some

'

', [3])]

transFresh dfa

2 [2

;

3] = [([2

;

3],

Some

'

', [])

;

([2

;

3],

Some

'

', [1])

;

([2

;

3],

Some

'

', [3])]

Explanation:

Starting from state

1

in nfa

2,

we can move only to state

2

'

'

and then from state

2

to state

3

on epsilon, which gives us the tuple

([1],

Some

'

', [2

;

3]) .'

'

is the only character in the alphabet. So

,

we return

[([1],

Some

'

', [2

;

3])] .

Starting from either state

1

or state

2

in dfa

2,

we want to see where we can move to

.

If we start at

1,

we can move to

2

'

',

and if we start at

2,

there isn't an

'

'

transition. There are no states we can move to from

2

via epsilons

(

because it's a DFA

),

so we have the tuple

([1

;

2],

Some

'

', [2]) .

Then, starting again from either state

1

or state

2,

we can move to

1

'

'

from

2,

and there isn't a

'

'

transition from

1

to another state. There are no states we can move to from

1

via epsilons, so we have the tuple

([1

;

2],

Some

'

', [1]) .

Then, starting again from either state

1

or state

2,

we can move to

3

'

'

from

2,

and there isn't a

'

'

transition from

1

to another state. There are no states we can move to from

3

via epsilons, so we have the tuple

([1

;

2],

Some

'

', [3]) .

,

our overall returned list is

[([1

;

2],

Some

'

', [2])

;

([1

;

2],

Some

'

', [1])

;

([1

;

2],

Some

'

', [3])] .

Starting from either state

2

or state

3

in dfa

2,

there is no

'

'

transition that starts from either state

2

or state

3 .

,

we have

([2

;

3],

Some

'

', []) .

Then, starting again from either state

2

or state

3,

we can move to

1

'

'

from

2,

and there isn't a

'

'

transition from

3

to another state. There are no states we can move to from

1

via epsilons

(

because it's a DFA

),

so we have

([2

;

3],

Some

'

', [1]) .

Then, starting again from either state

2

or state

3,

we can move to state

3

'

'

from

2,

and there isn't a

'

'

transition from

3

to another state. There are no states we can move to from

3

via epsilons, so we have

([2

;

3],

Some

'

', [3]) .

,

our overall returned list is

[([2

;

3],

Some

'

', [])

;

([2

;

3],

Some

'

', [1])

;

([2

;

3],

Some

'

', [3])] .

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock blur-text-image

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!

Fill in the ??? in the code: import java.io.*; import java.util.*; public class Lists { static final int QUESIZE = 20; // size of the processing queue static final int THROTTLE = 5; // number of...

Create a Java program named List that contains the following: o a doubly linked list that contains data for an integer named ProductID and a string named ProdType o allow the list to be filled by...

Please help me balance my post closing balance!!!!! I don't know where I made my errors. Accounting Cycle Project Solid Footing 9e Project is Activated Save>SAVING your project following these...

Answer all of the following questions completely. Using the PPC table below, calculate the opportunity cost of producing one more of one good in terms of the other (as asked below), between each...

I need to convert the Java Program from an ArrayList, back into an Array in Java. import java.io.*; import java.util.*; public class prog23 { public static void main(String[] args) throws IOException...

Please explain your code with comments and if the photos are too small to read, just open them in new tab or zoom in. Programming Assignment (50 points) 1. You are given a partially completed program...

I can't get my Post Trial Balance to equal out at the end, could someone help me find the error? Accounting Cycle Project Solid Footing 9e Project is Activated Save>SAVING your project following...

1. You are given a partially completed program hw05q1.c. You should follow the instructions given in the program to complete the functions so that the program executes as instructed. The program...

This is a Queue.java file which I need to write the code and I attached the Node.java and QueueTest.java file below as well. import java.util.NoSuchElementException; /** * A classic first-in...

Container.cpp ------------------------------- #include "Container.h" // Constructor for Container class Container::Container() { student = NULL; next = NULL; } -------------------------------...

Refer to the information for Zapato Company above. Zapato Company produces two types of boots: cowboy and cowgirl. There are four activities associated with the two products. Drivers for the four...

The McDonald Group purchased a piece of property for $1.2 million. It paid a down payment of 20% in cash and financed the balance. The loan terms require monthly payments for 15 years at an annual...

The face amount of the bond is called the what? principal contract annuity discount

Define the following medical terms: informed consent, implied consent, expressed consent, patient incompetence, emancipated minor, mature minor, subpoena duces tecum, respondent superior, res ipsa lo