Automata Exam 2

Question 1

Adfa stands for

Answer 1

acceptance problem for DFA

Question 2

Adfa is…

Answer 2

decidable

Question 3

Proof that Adfa is decidable pt1

Answer 3

Simulate B on input w

Question 4

Proof that Adfa is decidable pt2

Answer 4

If the simulation ends in an accept state, accept; if it ends in an non accepting state, reject

Question 5

Anfa is…

Answer 5

decidable

Question 6

For Adfa, B’s current state is

Answer 6

q0

Question 7

For Adfa, B’s current input position is

Answer 7

the leftmost symbol of w

Question 8

To prove Anfa is decidable

Answer 8

convert NFA B to equivalent DFA C

Question 9

Arex is..

Answer 9

decidable

Question 10

To prove Arex is decidable

Answer 10

convert REX to equivalent DFA A

Question 11

Edfa is…

Answer 11

decidable

Question 12

TM to prove a DFA accepts a string

Answer 12

1. Mark the start state of A
2. Repeat until no new states get marked
3. Mark any state that has a transition coming into it form any state that is already marked
4. If no accept state is marked accept; otherwise reject

Question 13

EQdfa test whether

Answer 13

two DFA’s recognize the same language

Question 14

For EQdfa C accepts..

Answer 14

only those strings that are accepted by either A or B but not both

Question 15

Formula for EQdfa

Answer 15

L(C) = ( L( A ) ∩ L( A’ ) ) ∪ ( L( B ) ∩ L( B’ ) )

Question 16

TM S for Acfg

Answer 16

1. Convert G to an equivalent grammer in Chomsky normal form
2. List all derivations with 2n-1 steps, where n is the length of w except if n = 0, then list all derivations with 1 step
3. If any derivations generate w, accept; if not, reject

Question 17

Prove Ecfg is decidable on input G where G is a CFG

Answer 17

1. Mark all terminal symbols in G
2. Repeat until no new variables get marked
3. Mark any variable where G has a rule A->U1,U2..Uk and each symbol has already been marked
4. if the start symbol is not marked, accept; otherwise reject