Reguläre Sprachen

Question 1

Wie ist ein (deterministischer) endlicher Automat definiert?

Answer 1

Question 2

Wann sagt man A ist die Sprache der Maschine M?

Answer 2

Wenn A eine Menge an Strings ist, die M akzeptiert

Question 3

Wie ist “Maschine M akzeptiert die Sprache A” definiert?

Answer 3

Question 4

Wann ist eine Sprache eine reguläre Sprache?

Answer 4

Wenn sie von einem endlichen Automaten akzeptiert wird

Question 5

Was ist eine Concatenation zweier Sprachen und wie ist sie definiert?

Answer 5

Question 6

Was bewirkt der Stern Operator auf eine bestimmte reguläre Sprache und wie ist dieser definiert?

Answer 6

It works by attaching any number of strings in A together to get a string in the new language.

Question 7

Was passiert, wenn es bei einem NFA das leere Wort als Übergang möglich ist?

Answer 7

If a state with an ε symbol on an exiting arrow is encountered, something similar happens. Without reading any input, the machine splits into multiple copies, one following each of the exiting ε-labeled arrows and one staying at the current state.

Question 8

Was ist das besondere an einem NFA?

Answer 8

Mehrere Übergänge für den selben Input sind möglich.

Question 9

Wie funktioniert es, dass ein NFA mehrere Übergänge für ein Input anbieten kann?

Answer 9

• After reading that symbol, the machine splits into multiple copies of itself and follows all the possibilities in parallelI
• If the next input symbol doesn’t appear on any of the arrows exiting the state occupied by a copy of the machine, that copy of the machine dies
• Finally, if any one of these copies of the machine is in an accept state at the end of the input, the NFA accepts the input string.

Question 10

Wie ist ein NFA formal definiert?

Answer 10

Question 11

Wer bindet stärker? Konkatenationsoperator oder der Vereinigungsoperator.

Answer 11

Konkatenationsoperator bindet stärker als der Vereinigungsoperator

Question 12

If k is the number of states of the NFA, wie viele Untermengen hat dann die Menge der Zustände?

Answer 12

2 hoch k

Question 13

Wie viele Zustände wird ein DFA maximal haben, um einen NFA darzustellen?

Answer 13

2 hoch die Anzahl der Zustände des NFA

Question 14

Was gilt für Q’ eines DFA’s, welcher von einem NFA aus konstruiert wurde?

Answer 14

Q’ = P(Q)

Q = Menge der Zustände vom NFA

Question 15

Was gilt für F’ eines DFA’s, welcher von einem NFA aus konstruiert wurde?

Answer 15

F′ = {R ∈ Q′| R contains an accept state of N}.

Question 16

Konstruktion eines DFA’s aus einem NFA

Was gibt die Funktion E(R) zurück?

Answer 16

For any state R of the DFA, we define E(R) to be the collection of states that can be reached from members of R by going only along ε arrows, including the members of R themselves. Formally, for R ⊆ Q let
E(R) = {q| q can be reached from R by traveling along 0 or more ε arrows}.