Week 2 Lecture 1 - NDFA to DFA Conversion

0.0(0)
studied byStudied by 0 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/5

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

6 Terms

1
New cards

What is the connection between languages accepted by an NDFA and a DFA?

The collection of languages accepted by a DFA and the collection of languages connected by an NDFA are the same. If there is a language accepted by a DFA, there must be an NDFA that accepts it, and vise versa.

2
New cards
<p><strong>Step 1 of NDFA to DFA conversion:</strong><br>Write out all the individual NDFA transitions for this automaton:</p>

Step 1 of NDFA to DFA conversion:
Write out all the individual NDFA transitions for this automaton:

q0 —a—> q1
q1 —a—> q1
q1—a—> q2
q1—b—> q1

3
New cards
<p><strong>Step 2 of NDFA to DFA conversion:</strong><br>Write out the transitions between sets of states, starting with the set containing the initial state, and considering all possible members of the alphabet for this automaton: </p>

Step 2 of NDFA to DFA conversion:
Write out the transitions between sets of states, starting with the set containing the initial state, and considering all possible members of the alphabet for this automaton:

knowt flashcard image
4
New cards
<p><strong>Step 3 of NDFA to DFA conversion:</strong><br>When no more DFA transitions can be found, draw the resulting automaton for this automaton:</p>

Step 3 of NDFA to DFA conversion:
When no more DFA transitions can be found, draw the resulting automaton for this automaton:

The initial state of the DFA is “the same” as in the NDFA and final states are those which contain a final state of the NDFA.

<p>The initial state of the DFA is “the same” as in the NDFA and final states are those which contain a final state of the NDFA.</p>
5
New cards
<p>What is different in conversion of NDFA to DFA when there are <span style="font-size: calc(var(--scale-factor)*14.35px)">λ transitions? Use this automaton:</span></p>

What is different in conversion of NDFA to DFA when there are λ transitions? Use this automaton:

Extra care is needed in step 1 to take account of λ transitions:

<p>Extra care is needed in step 1 to take account of <span style="font-size: calc(var(--scale-factor)*14.35px)">λ transitions:</span></p>
6
New cards
<p>What are the transitions if you were to convert this to a DFA?</p>

What are the transitions if you were to convert this to a DFA?

knowt flashcard image