4
What you draw is an NFA, because you do not have both transition for $a$ and $b$ in two accept states.
Indeed, you need 4 states at least. Because you have 4 different states:
Initial state
Detect $a^*$ strings
Detect $b^*$ string
None of them
You can't merge the first 3 steps because they are exclusive. Now, you can suppose that we can merge the 4th state ...
4
Since Büchi automata are strictly more expressive than LTL, such a translation is not possible in the general case.
For instance, the language $L = \{w_0 w_1 w_2 \ldots \in (2^{\{a\}})^\omega \mid \exists^\infty i \in \mathbb{N}. w_{2i} = \{a\} \}$ is representable by a Büchi automaton with 3 states, but is not expressible in LTL as it is a counting ...
3
I'm not sure what $L1, \dots, Lk$ are since you did not define them. The easiest way is probably that of starting with a DFA for $L$ and constructing a NFA for $drop(L)$ (hint in the spoiler below).
Then it should be easy to show that:
If $w \in drop(L)$ then the NFA accepts $w$: use the definition of the function $drop$ to conclude that there must be a ...
3
You've got the right idea, but there's a slight bug.
If you add an $\varepsilon$-transition from the start state to all accepting states, then the new machine recognizes a subtly different language.
Let $L_k = \{w_1 \cdots w_k : \exists u_1, \dots, u_{k-1} \in L(M) \text{ such that } w_1 u_1 w_2 \cdots u_{k-1} w_k \in L(M)\}$.
Note that $L_1 = L(M)$.
This ...
2
Your question was already asked before, but got no answer: How to prove for string of triplets that it is a Regular Language?. I merely summarize the comments given there.
You need to implement binary addition. That is easier when you consider first the language in reverse, the lower bits first.
Standard letters are (in a more intuitive notation) [00|0], [...
2
It took me a while to understand that your alphabet $\Sigma$ is $\{a,b\}$ and by /\ you meant the empty word $\epsilon$.
Your regular expression is the union of two sub-expression, namely:
(b + /\)(ab)*aa(ba)*(b + /\); and
(a + /\)(ba)*bb(ab)*(a + /\).
The first one (resp. second one) matches all the words that contain exactly one double letter, and that ...
2
Ellul, Krawetz, Shallit and Wang construct in their paper Regular Expressions: New Results and Open Problems a regular expression of length $n$ (for infinitely many $n$) such that the shortest string missing from its language has length $2^{\Omega(n)}$. Since a regular expression of length $n$ can be converted to an NFA having $O(n)$ states, this gives, for ...
2
Since your definition of $\epsilon$-closure isn't really a definition, it is impossible to prove anything using it. Instead, let me use the following definition: the $\epsilon$-closure of a set $S \subseteq Q$ consists of all states $x \in Q$ which are reachable from a state in $S$ by a (possibly empty) $\epsilon$-path (which is a path consisting of $\...
2
You're almost there. Yes, the intersection of two context-free languages is in general not context-free, but you have more structure here: one of your languages is regular! The intersection of a regular language and a context-free language is context-free, which gives us something to work with.
So. We have some DFA $M$, and we can build a PDA $N$ which ...
2
Sipser's book handles this case:
If at any point $S$ moves one of the virtual heads to the right onto a $\#$, this action signifies that $M$ has moved the corresponding head onto the previously unread blank portion of that tape. So $S$ writes a blank symbol on this tape cell and shifts the tape contents, from this cell until the rightmost $\#$, one unit ...
1
Your definition of $\epsilon$-closure is quite problematic. Here is a better formulation:
$\epsilon(S)$ is the intersection of all sets $T \subseteq Q$ such that (i) $T \supseteq S$ and (ii) if $q \in T$ then $\delta(q,\epsilon) \subseteq T$.
Here is a series of claims which imply $\epsilon(S) = \epsilon(\epsilon(S))$.
Claim 1. $\epsilon(S) \supseteq S$....
1
For an alphabet of $\{a, b, c\}$ constructing a DFA that accepts all strings not containing the substring 'aa' tells you several things about the number of states you need. Firstly, and this is true for any DFA, you need at least one accepting state. Since your DFA is meant to filter out some strings, it requires a 'trap' or 'dead' state, a state that may ...
1
The idea is to start with an automaton for $L$, and replace each transition labeled $\sigma$ by a path of length 2 both of whose edges are labeled $\sigma$. In order to make it a DFA, we also add a sink state. (This might be unnecessary in your definition of DFA.)
In more detail, suppose we start with a DFA $(Q,q_0,\delta,F)$ for $L$ (here $Q$ is the set of ...
1
You cant find the complement of a $TM$ for undecidable languages.
A decidable language is such that a $TM$ which recognizes language membership, always halts with a yes. In this case finding the complement of the machine is simple, just reverse the yes with the no, obtaining the complement of the original decision problem. I leave to you
the task of ...
1
No, that is not correct. Consider the following NFA over the one-symbol alphabet $\Sigma=\{1\}$:
,-----------------------.
|-----------. |
v | |
a --> b --> c --> d --> e --> f
|
V
g
Assume that all edges are labelled with the symbol $1$, except that the edges $a\to b$ and $a \to g$ are $\...
1
The induction you probably want is to show that a string $w$ ends in state $q_i$ iff it satisfies the property associated to that state.
The basis then is that the empty string, which must end in $q_0$, satisfies the property there.
You should be more precise in some of your properties. In $q_4$, the string ends in 01 as you state, but has never seen any ...
1
Here's some brief ideas on the pumping lemma that might help get you started.
Essentially the pumping lemma says:
Any DFA must have a cycle in it at some point. It takes at most $P$ transitions to go from the start state to the end of the cycle. We call $P$ the pumping length.
We can then break up any word $S$ into three parts:
The characters it takes to ...
Only top voted, non community-wiki answers of a minimum length are eligible
