# Tag Info

2

How about $L_1=\{\mathtt a^n\mid n\text{ is prime}\}$ and $L_2=\{\mathtt a^n\mid n\text{ is composite}\}$?

2

It is certainly possible for a Turing machine with alphabet $\{0,1\}$ to simulate a Turing machine with any finite alphabet. The idea is that if the larger alphabet has size less than $2^k$ then you can divide the tape into "chunks" of size $k$ and use each of these chunks to encode a single character from the larger alphabet. This requires a larger number ...

1

Possible solution: Build a DFA $A_1$ that accepts strings with $100$. Build a DFA $A_2$ that accepts strings with $110$. Build DFA $A$ that accepts strings with $100$ or $110$. The latter is the union of DFA's $A_1$ and $A_2$ (the union accepts a string iff it is accepted by $A_1$ or $A_2$). Here [ link ] (pp.3-5) you can find some example how to perform ...

1

Here is a NFA accepting your language, where I the an initial state, and F is a final state. It reads the word, and, in a non-deterministic way, choses to read one of the subword you want. Then, you "just" have to determinise it (be careful, it can have up to $2^8$ states… you may want to rewrite the NFA with less states)

1

Let $M=(Q,\Sigma, \delta, q_0, F)$ where the set of states is $$Q=\{q_0, q_1, q_{11}, q_{10}, q_f\},$$ the input alphabet is $$\Sigma = \{0,1\},$$ the transition function $\delta: Q\times \Sigma\to\ Q$ is defined by \begin{array}{c|c|c|c|c|c} \delta(q,b)& q_0 & q_1 & q_{11} & q_{10} & q_f\\\hline 0 & q_0 & q_{10} & q_f ...

1

Every connected grapgh $G$ is Eulerian grapg iff for every vertex $v\in V_G$, $deg(v)$ is even. Suppose $G$ is not connected, because for every $v\in V_g$, $deg(v)=p$, therefore every componnet of $G$ has at least $p+1$ vertecis, and that means $V_G>2p+1$ which leads to contradiction, so $G$ is connected. Also $\sum_{v\in V_G}deg(v)=p(2p+1)=2E$, therefore ...

1

In set theory, a set $x$ is transitive if for all $y$, if $y\in x$ then $y\subseteq x$. The (von Neumann) ordinals are defined to be the transitive sets that are well-ordered by $\in$. Thus the "$<$" relation between ordinals is simply $\in$. If $\alpha, \beta$ are ordinals with $\alpha\in \beta$, then $\alpha \subseteq \beta$. So any ordinal is a fine ...

1

In your description of the automaton the set of accepting states is missing. Assume now that the automaton is defined as $$(Q=\{q_0,q_1,q_2\},\Sigma=\{a,b\},\Delta,q_0,F=\{q_1,q_2\})$$ where the state transition function $\Delta$ is defined by the figure and $F$, the set of accepting states is defined so I could explain the results. You get "accept" first ...

1

The answer is simple By Dirac (1952) : A simple graph with n vertices ($n ≥ 3$) is Hamiltonian if every vertex has degree $\frac{n}{2}$ or greater. See https://en.wikipedia.org/wiki/Hamiltonian_path Since n is even, then 2 does not divides $n-1$. Thus $$d(v)\geq \frac{n}{2}$$

1

While (2,5,8) is an inclusionwise maximal independent set, it is not a maximum cardinality independent set. The graph parameter $\alpha(G)$ should be understood to mean the latter. In the example you give, (1,3,5,7,9) is another maximal independent set, and this one has greater cardinality. The existence of this set shows that we have $\alpha(G) \geq 5$. It ...

1

Yep, you're right. $y$ is the symbol that was written when the tape head moved. So the statement $$\delta(q, x_j) = (p, y, L)$$ should be read as "in state $q$, upon reading symbol $x_j$, write a $y$ on the tape, transition to state $p$, and move left".

1

To show that one of the statements is not true it suffices to give an example for which the statement is false. In the following example graphs the DFS is always started at node $s$ and the orientation of the edges indicates the search direction. Edges that are not oriented are not traversed during the search. For statements 1. and 3. consider the following ...

1

You get a tractable recurrence if, instead of considering where the largest number is, you look at the smallest number. The indexing will seem strange here, but bear with me. Let $f(n,l,r)$ denote the number of permutations of $\{0,\ldots,n\}$ where $l+1$ elements are visible from the left and $r+1$ are visible from the right. Clearly $f(n,l,r)=0$ if ...

Only top voted, non community-wiki answers of a minimum length are eligible