Finite Automata

Question 1

What does Deterministic Finite Automaton (DFA) consist of?

Answer 1

Question 2

What is a configuration?

Of a DFA

Answer 2

Question 3

What is a step relation? What is a reflexive transitive closure of ⊢?

Of DFAs

Answer 3

Question 4

How can DFAs be displayed as a transition graph?

Answer 4

Question 5

Which notation is used to be able to say that a word can be read by a DFA? Name a theorem connected to this idea.

Answer 5

Question 6

When is a language accepted by a DFA? When is a language regular?

Answer 6

Question 7

Why are DFAs deterministic?

Answer 7

Question 8

What happens to the complement of a language, if the language itself is regular? Show the basic steps of the proof.

Answer 8

Question 9

Finish the scentence. Give the basic steps of the proof.

Answer 9

Question 10

If two languages are regular, is their intersection, difference and union regular?

Answer 10

Yes

Question 11

What can be said about every finite language?

Answer 11

That it is regular.

Question 12

What is the difference between DFAs and Nondeterministic Finite Automata (NFAs)?

Answer 12

Question 13

What is the difference in definitions of the contents of NFAs?

Compared to DFAs

Answer 13

Question 14

What is the definition of a step relation in a NFA?

Answer 14

Question 15

What is a path?

In a NFA

Answer 15

Question 16

When is a language accepted by an NFA?

Answer 16

Question 17

When is an NFA regular?

Answer 17