Tag Info

New answers tagged

0

Start in state $q_i$ If you are an in state $q_i$ and read $a$ then move to $q_a$ If you are an in state $q_i$ and read $b$ then move to $q_b$ If you are an in state $q_a$ and read $a$ then move to $q_{aa}$ If you are an in state $q_a$ and read $b$ then move to $q_b$ If you are an in state $q_b$ and read $a$ then move to $q_a$ If you are an in ...


0

HINT: You’ll want to make the PDA non-deterministic, and I think that it’s easiest to have it accept by final state. The basic idea is to let it start by reading symbols without doing anything else. At any point when it’s reading a $0$ it can ‘decide’ to treat that $0$ as the beginning of a block of $0$s. Starting with that $0$ it pushes a symbol onto the ...


0

Note that $(a \mid b)^{*}$ means $\{\varepsilon, a, b, aa, bb, ab, ba, \dots \}$, so $(bb \mid b)^{*} = \{\varepsilon, b, bb, bbb, \dots \} = b^{*}$. That leads to $$R = (a \mid b) (bb \mid b)^{*} = (a \mid b) b^{*}$$ So the language created by $R$ is $L(R) = \{ a^lb^k \mid k \in \mathbb{N}_0, 0 \leq l \leq 1\}$. Converting your NFA to an equivalent DFA ...


5

$L_2 \cap L_3 = L_2 \cap \Sigma^* = L_2$ $L_2 \cup L_3 = L_2 \cup \Sigma^* = \Sigma^*$ $L_1 \cap L_3 = \Sigma^* \cap \Sigma^* = \Sigma^*$ $L_1 \cup L_2 = \Sigma^* \cup L_2 = \Sigma^*$


0

In your finite automaton there are three so called states: $A$, $B$ and $C$. The arrows tell us how we get from one state to another, and the arrow that points to $A$ out of nowhere tells us that the automation starts in state $A$. The automaton accepts a word if it ends in a final state. $A$ is a final state, as is has two circles around it. If we put the ...


0

That looks very good, and I think you certainly have the right idea. I see one minor mistake: I think the labels are switched on the two bottommost arrows labeled a and b. If I understand correctly, that accepting node represents strings that can be generated from $B$, and the two arrows below it represent the $B\to\mathtt{ba}B$ production, so the b arrow ...


1

have a stack that recognizes 2 symbols for 'a', first beginning from the left reading all the a's and pushing 1 a onto the stack for each a then once you reach the first b, if there is a 'a' on the stack then change it to say a 'ha' <- for half a, then move right, if there is another b we can now pop the 'ha' off the stack and continue, if there is a 'a' ...


1

You asked “How would I go about designing…”. You should imagine that someone has given you a very long string of symbols and asked you to verify this property. The string is so long—perhaps thousands or millions of symbols—so that you cannot simply see it at a glance, as you can with short strings like ababab. Then ask yourself what you could do to decide ...


0

$q_0$- initial state $q_1$-starts with 'a' $q_2$-starts with 'ab', accepting state $q_3$-starts with 'b'/'aa' Now, note that if a word starts with 'ab' then it's legal iff the remainder of the word is legal, and once we found that a word is ruined somewhere then there is no redemption for this words. Also, note that you can merge $q_0$, $q_2$ Now use ...


2

I’m going to assume that the picture shows two distinct DFAs, and that the blue states are the acceptor states. The top DFA accepts precisely those strings that contain exactly two $b$s and end with a $b$; the corresponding regular expression is $a^*ba^*b$. The strings of that kind of length at most $4$ are $$bb,abb,bab,aabb,abab,baab\;.$$ It’s a little ...


1

For Every symbol of the alphabet, there is only one state transition in DFA. We do not need to specify how does the NFA react according to some symbol. DFA can not use Empty String transition. NFA can use Empty String transition. DFA can be understood as one machine. NFA can be understood as multiple little machines computing at the same time. DFA will ...


0

First you should be able to convert the regular expression into a graph like this: Then processing an input corresponds to following a path along this graph, so after each input character we "are" at one of the red dots. However, we may sometimes be at several red dots at the same time because it is usually not clear which path is the "right" one until ...


1

You can follow the following steps. Each step is meant to be realized by an algorithm, not manually: Convert the regular expression to a NFA. Convert the NFA to an equivalent DFA. If the FSA that you have defined is a NFA, convert it to an equivalent DFA. Test the two DFAs for equivalence. Edit: There is an online implementation of the first two steps ...


0

You can also check C.Papadimitriou, Computational Complexity where Turing Machines are defined unambiguously, in my opinion. What do you mean by "real conceptual problem'? I don't get it. But since Turing Machines can solve any, solvable problem I'll say there is. Turing Machines (TM) are used in nowdays literature as theoretical computational model to ...


1

This equivalence is called the Nerode equivalence of $L$. The set of equivalence classes is in bijection with the set of states of the minimal DFA of $L$. To be more precise, for each word $u$, the equivalence class of $u$ is $[u] = \{ v \in A^* \mid uv \in L\}$. Now the minimal DFA of $L$ is $\mathcal{A} = (Q, \cdot, i, F)$ with $Q = \{ [u] \mid u \in A^* ...


2

Let $\mathcal{A}$ be a DFA with initial state $q$. Since $q \cdot a = q$, one has $q \cdot a^n = q$ for all $n \geqslant 0$. Therefore if $q$ is a final state, then $a^* \subseteq L(\mathcal{A})$ and if $q$ is not a final state, then $a^* \cap L(\mathcal{A}) = \emptyset$.


1

$L=\{a^ib^jc^k|i<j<k\}$ let $n<i$ and $s=uvwxy$ and $s\in L$ then pumping lemma $|vx|>0$ and $|vwx|\leq n$ implies $vwx$ contains either one alphabet ($a$, $b$ or $c$) or two alphabet ($a,b$ or $b,c$) not three alphabets (since $n<i$) let us assume it contains alphabets $a$ and $b$ (i.e $v$ contains $a$ and x contains $b$) by pumping lemma ...


1

I think that it is not a "real conceptual problem". But if you want an unamboguous coding, you can see Wang coding, described in George Boolos & John Burgess & Richard Jeffrey, Computability and Logic (5th ed - 2007) : Ch.8.1 Coding Turing Computations, page 88-on.


1

If you are in state $\{2,3,4\}$, on input $a$ you can go to $\{2,3\}$, because those are the only states reachable from states $2$, $3$, and $4$ on input $a$. Similarly, if you are in state $\{2,3,4\}$, on input $b$ you can go to $\{1,2,3\}$, because those are the states that can be reached in the NFA on input $b$ from $2$, $3$, and $4$.


1

Let's say your graph has $n$ nodes. Degree of every of nodes is at least $0$ and at most $n-1$. If there is a node $v$ of degree $\deg(v) = 0$, then there cannot be a node $w$ of degree $\deg(w) = n-1$ and vice versa, therefore there are only $n-1$ possible different degrees of $n$ nodes. By Pigeon-Hole principle at least two nodes are of the same degree.


1

Suppose your graph has n nodes. There are only n-1 possible values for the degree of the nodes, so with pigeon hole, at least 2 have the same degree. Oops, there is a special case where a node could have degree 0, but then your problem reduces from n to n-1. And you still have to prove it for n = 2.


0

OK, the regular language expression should be: (a(aa)*b(bb)*(aa)*)U((aa)*(bb)*a(aa)*) meaning, as you already stated: either the first block of a's and b's should each have an odd number, and the second block of a's should have an even number, or the first block of a's and the b's should have an even number, and the second block of a's should have an odd ...



Top 50 recent answers are included