Automata Exam 2 Flashcards Preview

Programming > Automata Exam 2 > Flashcards

Flashcards in Automata Exam 2 Deck (17):
1

Adfa stands for

acceptance problem for DFA

2

Adfa is...

decidable

3

Proof that Adfa is decidable pt1

Simulate B on input w

4

Proof that Adfa is decidable pt2

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

5

Anfa is...

decidable

6

For Adfa, B's current state is

q0

7

For Adfa, B's current input position is

the leftmost symbol of w

8

To prove Anfa is decidable

convert NFA B to equivalent DFA C

9

Arex is..

decidable

10

To prove Arex is decidable

convert REX to equivalent DFA A

11

Edfa is...

decidable

12

TM to prove a DFA accepts a string

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

13

EQdfa test whether

two DFA's recognize the same language

14

For EQdfa C accepts..

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

15

Formula for EQdfa

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

16

TM S for Acfg

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

17

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

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