# Tag Info

0

Parsers & compilers usually utilize deterministic finite automata to parse input. They may use DFAs for lexical analysis (identifying tokens), but the "heavy lifting" is going to be done using more powerful algorithms: for example, recursive descent, LALR(1), LL(*), etc. You might find this table enlightening.

1

3 ([1-579]* 6[1-579]* 6)* [1-579]* where [1-579] denotes one of {1,2,3,4,5,7,9}.

1

As per your last thread, note the syntax $(x + y)$ says to choose exactly one of $x$ or $y$. So let's define $(1 + 2 + 3 + 4 + 5 + 6 + 7 + 9)$. Notice how I concatenate two $6$'s together. Now if I take $3((1 + 2 + 3 + 4 + 5 + 6 + 7 + 9)^{*}6^{*}(1 + 2 + 3 + 4 + 5 + 6 + 7 + 9)^{*}6^{*})^{*}$, I get an even number of $6$'s, if there are any at all. With your ...

1

Some comments: It seems that $\varepsilon$ denotes an empty string (some authors use $\lambda$ for that). Symbol $\$$is a frequently used out-of-alphabet symbol, here to mark the end of the stack, i.e. to know when the word should end. Symbol \varnothing on the right is most probably "reject state". Notation \varepsilon \to a would be then pop ... 0 I'll use | for alternation (I think this is more standard than +). For your first example, if you have a tt in your expression, you won't be able to have any s before it. I think this works:$$(t)^*t(s)^*t(st\,|\,s)^*$$In the second problem, you need an stts, and the strings on the right cannot start with an s and cannot have two consecutive ... 1 For 1, one must be carefiul to include variants starting with at least two t: ttt*(s+st)* Then there are the variants starting with one t: tss*t(s+st)* And those starting with no t: ss*tss*t(s+st)*. These can be nicely combined into (tt*+s*tss*)t(s+st)*, a pattern one might not have guessed out of the blue. 1 For the first language$$ b^2b^*(1+a) + (ba + aa^*ba)a^*b(1 + a) $$For the second language$$ (aa^*b + bb^*ab)(ab + bbb^*ab)^*ba(bb^*a)^* $$0 You just need 6 states: initial state 1, final state 6. 1 \xrightarrow{0} 2 \xrightarrow{0} 4 \xrightarrow{1} 5 \xrightarrow{1} 6 \qquad 1 \xrightarrow{1} 5 \qquad 2 \xrightarrow{1} 3 \xrightarrow{0} 5 0 Start at state q_{0}. On input of a, transition to state q_{1}. On input of b, go to q_{2}. While on q_{1}, if there is an input of a, go to q_{0}. While on q_{2}, if an input of b, go to q_{3}. On q_{3}, on input of b, go to q_{4}. While on q_{4}, go to q_{2} on input of b. The accepting states are q_{0} and q_{4}. ... 0 Sorry, I'm no good at drawing diagrams so you will have to draw one yourself. State q_0 is the initial state and q_4,q_7,q_9 are accepting states.$$\matrix{\hbox{state}&0&1\cr q_0&q_1&q_8\cr q_1&q_2&q_5\cr q_2&q_{10}&q_3\cr q_3&q_{10}&q_4\cr q_4&q_{10}&q_{10}\cr q_5&q_6&q_{10}\cr ... 2 Here$q'$is just being used to denote "another state". Fairly frequently (outside of calculus), we use primes ($q'$), or tildes ($\tilde{q}$), or carats ($\hat{q}$), etc. over the same letter to signify another object of the same type. This improves readability, because there is a visual identification of that letter with that type of object. 1 Just reason through it. Can the first letter be 'a' or 'b'? Yes, so you should have two transitions coming from the initial state. If you saw an 'a', what can you see next? Anything right? Well this sounds like the same situation as the initial state, so loop back. Now what if you saw a 'b' first? Can you see a 'b' or an 'a' next? Yes, you can see ... 1 This is not correct. Consider$abbbab$. Similarly, I can run$abab$and it will be accepted. On state$q_{0}$, you can keep looping on an input of$a$. On an input of$b$, go to state$q_{1}$. Stay at$q_{1}$on an input of$b$, and transition to state$q_{2}$on an input of$a$. Transition from state$q_{2}$to$q_{0}$on an input of$a$. For$q_{1}$and ... 0 ml0105's solution is correct however if you consider the problem as creating ONE automaton to recognize$L(M_{1})-L(M_{2})$you need to do something else... first you create an automaton to accept$\overline{L(M_{2})}$, for that it's enough to transform any final (accept) state to non-final and vice versa; then you need to make an automaton to accept ... 0 Your set theoretic notation is correct, but think about it in terms of running the automaton on an input. You take a string$\omega \in \Sigma^{*}$. Run it through$M_{1}$. If it accepts, run it through$M_{2}$. If$M_{2}$accepts$\omega$, reject. That's how you construct your automaton to recognize$L(M_{1}) - L(M_{2})$. -1 You have b*(a+b)*a* that matches words without abb. Split the string on its first a. On the left it will have b* and on the right it will have (a+b)*a*. The two b can be both on left, one on left and one on right or both on right side. That's three cases. In each case two things of the form x* have to turn into xx*. bbb*(a+b)*a* bb*(a+b)(a+b)*a* ... 0 I'm guessing it's similar to the notation used in this post on CS, where the author uses it to mean OR. Applying to your example, your FSM must accept an even number of as, or a number of bs divisible by three. So, to draw the graph, first draw the graph for$(a^2)^*$. Then, draw the graph for$(b^3)^*$. Then, put a start state, say$s$, and transitions ... 0 If your goal is to prove that$L$is undecidable, you want to reduce from the halting problem, not to the halting problem. This reduction is easy enough if$S$is not empty. Suppose we're given$(M,a)$and want to decide whether$M$halts on input$a$. Construct machine$M'$to do the following: Ignore its input. Write$a$to the tape. Simulate$M$. ... 0 You haven't defined S, but it has to be defined in order for the problem to be specified. If S is a finite set, in order to solve your problem it would suffice to be able to solve, for each$i$in S, the problem of whether$M$halts on input$i$. But if S is infinite, that may not be enough. 0 Your proof idea is just fine. If you want to make the proof even clearer, all you have to do is set$S = \{w\}$for an arbitrary string$w$and set$n=1$, and now you have the halting problem. So if you could decide your problem for arbitrary$S,n$, then you could decide the halting problem, which is impossible. If you want to rigorously show the problem is ... 2 Hint. A non-empty word whose length is a multiple of$3$has either length$3$or consist of a non-empty word whose length is$3$and a non-empty word whose length is a multiple of$3$. 1 This shouldn't be possible. Hint: Consider the following two context-free languages over the alphabet$\{ \mathtt{a},\mathtt{b},\mathtt{c},\mathtt{d} \}$:$L_1 = \{ \mathtt{a}^n\mathtt{b}^n\mathtt{c}^k\mathtt{d} : n,k \geq 1 \}$;$L_2 = \{ \mathtt{a}\mathtt{b}^\ell\mathtt{c}^\ell\mathtt{d} : \ell \geq 1 \}$. Now identify the language $$L = \{ w \in L_1 ... 0 I think I am beginning to understand this. I do not know how to do a diagram on here so this description might be a little rough: \rightarrow q_0$$\rightarrow (a,0,11)$$\rightarrow q_1$$\rightarrow (b,11,\lambda) \: and \: (b,111,\lambda)$$\rightarrow q_2$$\rightarrow (\lambda,0,\lambda)$$\rightarrow q_3 with q_1 \rightarrow (a,1,11) \rightarrow q_1 ... 0 Hint for (a): I think you need more states than you said. Here's my idea. Every time the machine reads an a, it should push a token on the stack. Eventually there will be n tokens on the stack. When the machine starts seeing bs it should use its finite control to keep count of how many it has seen. After it reads 2 bs, it should nondeterministically ... 1 You need to store in the finite state how many 0s and how many 1s have been seen. So let the states be pairs of the form \langle n_0, n_1\rangle where n_0 is the number of 0s and n_1 is the number of 1s seen so far, with 0\le n_0\le 2 and 0\le n_1\le 3. The start state is \color{green}{\langle 0,0\rangle}. On reading a 0, the machine makes a ... 2 It is possible, you could show it using regular expressions and closure properties. Let L_1 = (\Sigma^*\mathtt{0}\Sigma^*\mathtt{0}\Sigma^*) and L_2 = (\Sigma^*\mathtt{1}\Sigma^*\mathtt{1}\Sigma^*\mathtt{1}\Sigma^*), then$$X = \big\{s \in \Sigma^* \mid \#_\mathtt{0}(s) \geq 2, \#_\mathtt{1}(s) \leq 2\big\} = L_1 \cap L_2^c$$If you want to construct ... 1 The Myhill-Nerode theorem shows this immediately. The infinitely many prefixes 0^i11 are all pairwise distinguishable. (If i\ne k, then 0^i is a distinguishing extension: 0^i110^i \in A but 0^i110^k\notin A). Therefore the language cannot be regular. As for your attempt to use the pumping lemma, I'm not entirely sure how the formulation of the ... 6 Firstly here is some data for S(x,y): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ------------------------------------------------------------------------------------------------------------------------------------------------------- 1 | 2 ... 0 If A is the alphabet, then f(L) = L - LA^+. 0 as you want to draw a NFA, trap state is not necessary. but, if you want to draw a DFA, as you know, all states should have exactly one vertex going out of each state. so, we are forced to draw a new state(named TRAP), and transfer all unused vertex to that state. in your question, for example, state q3 haven't outgoing vertex by 'a' , 'b' and it is not a ... 0 be careful that your machine should read 'a' to accept destination state. in your nfa, before reading 'a', 2 lambda transitions should be placed. first, to go to q2, and second, to go to q0. after that your machine can read a 'a' and places on q1. now transition to q2 and q0 are take placed by one and two lambda transitions. good luck 0 You can use the Myhill-Nerode theorem. Define equivalence relation on \{1\}^*$$x R_L y \Leftrightarrow \forall z\in\{1\}^*, (xz\in L \leftrightarrow yz\in L)$$The theorem states that L is regular if and only if this relation produces finitely many equivalence classes, which means that there will be a minimal DFA (one state for each equivalence class) ... 0 Let L be the given language and suppose for a contradiction that L is regular. Then, by the Pumping Lemma there must exists some positive constant p > 0 such that any string in L of length at least p can be pumped. Consider the string w = 1^{p^2} \in L. Since |w| = p^2 \geq p, we can split w in three parts x,y,z, that is, we can write w ... 3 Suppose (for contradiction) that the language L is recognized by a DFA M=(Q,Σ,δ,q_0,F). You have to show that M has infinitely many states and so it is not a finite automata, giving the desired contradiction. 3 Hint One usually derives a contradiction via the Pumping Lemma. 0 So M_{1} and M_{2} are Turing Machines such that L(M_{1}) = L_{1} and L(M_{2}) = L_{2}. Since L_{1}, L_{2} are recursively enumerable, given a string \omega, if \omega \in L_{i}, then M_{i} will halt and accept \omega. So the proof is by simulation. Consider a Turing Machine M on input \omega. It simulates M_{1} and M_{2} on ... 3 How easy this is to state depends on what definition of recursive you are using, I'll use the second one on Wikipedia: A recursive language is a formal language for which there exists a Turing machine that, when presented with any finite input string, halts and accept if the string is in the language, and halts and rejects otherwise. The Turing machine ... 3 Yes, f(L) is regular if L is. Hint. Take a deterministic finite automaton whose language is L and remove all the outgoing transitions from the accepting states. 1 Start with making a table that describes the "moves" of the NFA. One row for each state and one column for each input symbol. Then in each sell (i,j) you write the states in which the NFA goes to when it is at the state of row i and reads the symbol of column j. For example, when it is in state 0 and reads a, it will go to states 0 and 1. ... 1 Such a regular language does not exist, and it is because of the following: Given any regular language L, the language L^\prime consisting of all proper prefixes of words in L is regular. Let L be a regular language, and fix a DFA D = ( Q , \Sigma , \delta , q_0 , F ) accepting it. Consider the DFA D^\prime = ( Q , \Sigma , \delta , q_0 , ... 3 Let L_1=\emptyset, L_2=\Sigma^*. I think not. 0 Say L is a regular language accepted by M = \langle S, i, F, \Sigma, \delta\rangle where S is the set of states, i the start state, F\subset S the set of accepting states, \Sigma the input alphabet, and \delta : S\times \Sigma \to S the transition function. We define M' as follows: Its input alphabet is \Sigma, the same as for M. Its ... 0 Hint: Let M be a DFA for language L. We want to construct M', a DFA for language \operatorname{exchange}(L). The automaton M' reads a_n first, and can store the value of a_n in its finite control until the end. It can then simulate the behavior of M on the following input a_1a_2\ldots a_{n-1}. When it reaches the end of the input, it ... 0 Hint: \{a^nb^m \mid n < m\} = \{a^nb^n \mid n \in \mathbb{N}\} \circ \{b^k \mid k \geq 1\} \{a^nb^m \mid n > m\} = \{a^k \mid k \geq 1\} \circ \{a^nb^n \mid n \in \mathbb{N}\} Assuming that X generates \{a^nb^n\}, start with S \to XB \mid AX. I hope this helps \ddot\smile 0 You have two cases like your professor stated: n > m and n < m. Let x \to c_1 and x \to c_2 be two rules that initiate the two cases, i.e. x is the start variable. Then for example, for n > m this is handled by c_1 and the context free grammar rules to generate it are c_1 \to a, c_1 \to a c_1 b, and c_1 \to a c_1. Similarly for ... 4 The first language consists of all words on a,b that are the same as their reversed-string. Since this is the definition of a palindrome, this language contains all palindromes. In the second language, we construct palindromes by concatenating a string with its reverse. For example, taking w = abb, we note that abbbba is in L. Note that while ... 0 You want a regular expression that is any number, k, of a's, followed by a b, followed by: an even number of a's if k is odd. an odd number of a's if k is even. So after some guessing... L = a (aa)^* b (aa)^* \ | \ (aa)^* b (aa)^* a. To do the FSM, you just add nodes as you need them... there's probably algorthms that can ... 1 Yes, L is regular and the language W=\{w\} is regular (finite languages are always regular). By closure properties of regular languages, L-W is regular. 0 When you write something like$$S \to abA\,|\, A \,|\, B$$that is actually an abbreviation for three separate productions$$S \to abAS \to AS \to B$$The last two are unit productions, since their right side consists of exactly one variable. 0 The first language is the set of palindromes over$\{a, b\}$. The second language is the set of all strings over$\{a, b\}$. Clearly these are not the same language. The grammar for$L_{palindrome}$is:$S \to \epsilonS \to aS \to bS \to aSaS \to bSb\$ For the second language, there are only two states, both accepting. Both states ...

Top 50 recent answers are included