Neue Frage

2012.03.19 Task 6 c solutions

gefragt 2017-08-25 15:28:54 +0200

Anonymer Benutzer


Hi there,

if these two automatons are different, how can i transofrm the acceptance condition of A 1 to Fa ∨ Fq ?

– A 1 =A ∃ (V, φ I , φ R ,Fa ∨ Gb)

– A 2 = A ∃ (V, φ I ∧ q, φ R ∧ b ∧ q ∧ q ʹ , Fa ∨ Fq)

bearbeiten retag Als beleidigend melden schließen löschen

1 Antwort


geantwortet 2017-08-25 17:55:17 +0200

PS Gravatar-Bild

I am not sure what you are actually asking for. But let me try to answer anyway.

In the lecture slides, you will find the following equivalence using a nondeterministic automaton:

Gφ = A∃({q},q,φ∧q∧q′,Fq)

Note that this automaton has only a single state with a self-loop labeled with φ. Hence, if there is an infinite run through the automaton at all, it must satisfy Gφ and also Gq since we can only loop in the initial state {q}. The acceptance condition Fq of this automaton is somehow fake, since you could also write there many other conditions like true or GFq or FGq or also Gq, in particular, any condition implied by G(φ∧q).

But that is not what has been asked for in that exam. You should reason about equivalence of automata, and how you may rewrite/simplify them. A2 can be simplified as follows: By the initial condition and the transition relation, every run must always satisfy q similar to the explanations above. Hence, without changing the acceptance of the automaton, you can add a conjunction with Gq to the acceptance condition:

A2 = A∃(V,φI∧q,φR∧b∧q∧qʹ,(Fa ∨ Fq)∧Gq)

You may also say that q is somehow useless since the only runs we can look at will always have q=1 in every state. Thus, also without changing the meaning of the automaton, you can replace q with 1 everywhere and eliminate the useless state variable. That gives you the following equivalent automaton:

A2 = A∃(V,φI,φR∧b,true)

Next, any run through this automaton must always satisfy b: Even though the initial condition does not demand this, only states where b holds have outgoing transitions. For this reason, you can now rewrite it also to the following equivalent form:

A2 = A∃(V,φI,φR,Gb)

Now, you can see that A1 accepts all words that are accepted by A2, but A1 may also accept words by Fa which is not considered by A2.

Coming closer what you may really ask: Working back the above steps that I have showed you for A2, you may do the same for A1. BTW, you can first join Fa ∨ Fq into F(a∨q).

Does that help?

bearbeiten Als beleidigend melden löschen publish Link mehr


A ∃ (V, φ I , φ R ,Gb) = A ∃ (V, φ I ∧ q, φ R ∧ b ∧ q ∧ q ʹ ,Fq) and A ∃ (V, φ I , φ R ,Fa ∨ Gb) != A ∃ (V, φ I ∧ q, φ R ∧ b ∧ q ∧ q ʹ , Fa ∨ Fq) right?

Jonas ( 2017-08-25 18:47:15 +0200 )bearbeiten

Yes, right.

PS ( 2017-08-26 16:00:02 +0200 )bearbeiten

Ihre Antwort

Du kannst deinen Eintrag bereits als Gast verfassen. Deine Antwort wird zwischengespeichert, bis du dich eingeloggt oder registriert hast.
Bitte nur konstruktive Antworten auf diese konkrete Frage posten.
Falls du eine Frage stellen willst, dann stelle eine neue Frage.
Für kurze Diskussionen und Nachfragen benutze bitte die Kommentar-Funktion.
Deine Fragen und Antworten kannst du jederzeit nachbearbeiten und verbessern.
Gute Fragen und Antworten kannst du mit einem Upvote oder Downvote bewerten.

Schreibe deine Antwort auf diese Frage

[Vorschau ausblenden]


Gefragt: 2017-08-25 15:28:54 +0200

Gesehen: 33 mal

Letztes Update: Aug 25