Dtjytyk

How to format long polynomial?

RSA: Danger of using p to create q

Accidentally leaked the solution to an assignment, what to do now? (I'm the prof)

Modeling an IP Address

LaTeX: Why are digits allowed in environments, but forbidden in commands?

Why is consensus so controversial in Britain?

Why can't I see bouncing of a switch on an oscilloscope?

Intersection point of 2 lines defined by 2 points each

Are the number of citations and number of published articles the most important criteria for a tenure promotion?

Why do I get two different answers for this counting problem?

What are these boxed doors outside store fronts in New York?

Are astronomers waiting to see something in an image from a gravitational lens that they've already seen in an adjacent image?

Why "Having chlorophyll without photosynthesis is actually very dangerous" and "like living with a bomb"?

Could an aircraft fly or hover using only jets of compressed air?

Roll the carpet

dbcc cleantable batch size explanation

What typically incentivizes a professor to change jobs to a lower ranking university?

Is it tax fraud for an individual to declare non-taxable revenue as taxable income? (US tax laws)

Replacing matching entries in one column of a file by another column from a different file

Can I ask the recruiters in my resume to put the reason why I am rejected?

Important Resources for Dark Age Civilizations?

Was any UN Security Council vote triple-vetoed?

Perform and show arithmetic with LuaLaTeX

Maximum likelihood parameters deviate from posterior distributions

Show that no Büchi Automaton with less than 3 states exists for the LTL formula $ G(p_1rightarrow XFp_2) $

Number of states required for deterministic finite automataWould the following NFA accept all strings?Connection of closed subsets of $A^{omega}$ and deterministic Büchi-Automata, Question from Book: Infinite Word by D. Perrin & J.-E. PinConstructing a finite automata from a subset of its languageProve that a PDA with accept states accepts all context-free languagesregular language proof, a language partial to a regular oneBest approach to determine the equivalence classes of a formal languageDoes finite automata take an alphabet or language as input?A finite set of infinite words is $omega$-regular.How do I show that this DFA accepts this string?

0

$begingroup$

Given the LTL formula $ G(p_1rightarrow XFp_2) $, show that there is no Büchi-automaton which recognizes the same set of $ omega $-words $ alpha in ({0,1}^2)^omega $ with less than three states.

My general idea is a proof by contradiction: Assuming that there is an automaton $ A $ with less than three states and accepting the words described by the LTL formula, I try to find a $ omega $-word which is also accepted by the automaton but is not described by the LTL formula. This would be a contradiction and so the assumption would be wrong.
The only set of $omega $-words which do not fulfill the LTL formula have the form $ binom{*}{*}^* binom{1}{0}^omega $.

However, at this point I do not know how to show that a automaton with less than 3 states which accepts the words of the LTL-formula could also accept this word.

I would really appreciate your help.

formal-languages automata

share|cite|improve this question

edited Mar 20 at 10:36

Ben

asked Mar 19 at 14:47

BenBen

13

$endgroup$

add a comment | 

0

$begingroup$

Given the LTL formula $ G(p_1rightarrow XFp_2) $, show that there is no Büchi-automaton which recognizes the same set of $ omega $-words $ alpha in ({0,1}^2)^omega $ with less than three states.

My general idea is a proof by contradiction: Assuming that there is an automaton $ A $ with less than three states and accepting the words described by the LTL formula, I try to find a $ omega $-word which is also accepted by the automaton but is not described by the LTL formula. This would be a contradiction and so the assumption would be wrong.
The only set of $omega $-words which do not fulfill the LTL formula have the form $ binom{*}{*}^* binom{1}{0}^omega $.

However, at this point I do not know how to show that a automaton with less than 3 states which accepts the words of the LTL-formula could also accept this word.

I would really appreciate your help.

formal-languages automata

share|cite|improve this question

edited Mar 20 at 10:36

Ben

asked Mar 19 at 14:47

BenBen

13

$endgroup$

add a comment | 

$begingroup$

Given the LTL formula $ G(p_1rightarrow XFp_2) $, show that there is no Büchi-automaton which recognizes the same set of $ omega $-words $ alpha in ({0,1}^2)^omega $ with less than three states.

My general idea is a proof by contradiction: Assuming that there is an automaton $ A $ with less than three states and accepting the words described by the LTL formula, I try to find a $ omega $-word which is also accepted by the automaton but is not described by the LTL formula. This would be a contradiction and so the assumption would be wrong.
The only set of $omega $-words which do not fulfill the LTL formula have the form $ binom{*}{*}^* binom{1}{0}^omega $.

However, at this point I do not know how to show that a automaton with less than 3 states which accepts the words of the LTL-formula could also accept this word.

I would really appreciate your help.

formal-languages automata

share|cite|improve this question

edited Mar 20 at 10:36

Ben

asked Mar 19 at 14:47

BenBen

13

$endgroup$

share|cite|improve this question

edited Mar 20 at 10:36

Ben

asked Mar 19 at 14:47

BenBen

13

share|cite|improve this question

edited Mar 20 at 10:36

Ben

asked Mar 19 at 14:47

BenBen

13

asked Mar 19 at 14:47

BenBen

13

asked Mar 19 at 14:47

BenBen

13