Tagged Questions
0
votes
0answers
14 views
Shortest trace for LTL
Given a finite trace semantics for LTL (one where u,i |= X phi does not hold if i = |u|) is there a better bound of the length of a minimal trace for a satisfiable formula ?
By better, I mean better ...
1
vote
2answers
75 views
How to prove that the following language is not regular?
This is the following problem that I've been having difficulty on:
For this problem, we will show that there are non-regular languages over the alphabet $\{0\}$. The language that will be used is the ...
1
vote
2answers
78 views
How can I prove the majority of three languages is also regular if the three languages are regular?
This is a question I've been stuck on recently:
Let $A$, $B$, and $C$ be three languages over the same alphabet. Define $\mathrm{maj}(A,B,C)$ to be the collection of all strings $w$ that occur in at ...
4
votes
3answers
129 views
Deciding equivalence of regular languages
Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows:
build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) ...
