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