# Tag Info

4

Looking from the final state $q_2$: $$u(0|1)^*$$ Arrival only via accepting a $1$ from $q_1$ or $q_0$: $$v1(0|1)^*$$ Joining the start state $q_0$: $$(0|\epsilon)1(0|1)^*$$ Noting the back loop $q_1\to q_0$, so we can have $q_0\to q_2$ via $1$ or $q_0\to q_1\to q_2$ via $01$ or $q_0\to q_1 \to q_0 \to q_2$ via $001$ etc. accepting $0^*1$: $$... 2 Any path from the start state to an accept state is a string in your language, and if you find a loop from a state A back to itself then you can repeat the loop string as many times as you want after you reach A and then if you can reach an accept state from A then this will lead to an infinite family of accepted strings where the loop string is repeated ... 5 This is a very small DFA, so I’d use a fairly ad hoc approach. Notice first that its language is precisely the set of words that reach q_2: once it gets to q_2, it stays there, and there is no other acceptor state. Thus, we need only see what words get to q_2. Clearly we need a 1 at some point. It can come right away, thanks to the ... -1 It seems to be part of a normalization for the sake of convenience. The traditional definition would work as well. Citing from [HanWood2004] "The Generalization of Generalized Automata: Expression Automata" Definition 2. An expression automaton A is specified by a tuple (Q, \Sigma, \delta, s, f ) , where Q is a finite set of states, \Sigma ... 0 Question. What are the common features of your three problems? Answer. You have to count some parameter modulo n for a certain n. For (1), you have to count |u|_a modulo 2, for (2), you have to count |u|_b modulo 4 and for (3) you have to count |u| modulo 3. If you have this in mind, you can easily design a DFA for each situation. I will ... 2 Your answer to 1 is almost correct: It does not accept strings with zero as such as bc. And it does not accept for example acba. Try something like$$ [bc]^*(a[bc]^*a[bc]^*)^*$$Based on this, you should have littel problems to find a regex for 4k number of bs and then 4k+1 number of bs For the third task, first solve "length equals 3", then ... 1 Spoiler alert. My solutions. 1)$$ L ::= Bc \mid Cd \\ B ::= aBbb \mid \epsilon \\ C ::= aaCb \mid \epsilon $$2)$$ L ::= A \mid B \\ A ::= b \mid aAaa \\ B ::= aaba \mid aaBa $$Notice that the base case of the B recursion is aaba, not \epsilon. This removes ambiguity. 2 Suppose that the set of all primes is regular. Then it is recognised by a DFA with say m states. Let p be a prime whose binary expansion ends with m zeros and a 1, so that$$p=\underbrace{\cdots\ \cdots\ \cdots}_{n\ \rm in\ binary}\, \underbrace{00\cdots00}_{m\ \rm zeros}1=2^{m+1}n+1$$for some n. (We know that there is such a prime from ... 1 The decomposition into xyz is dependent on what input string 0^p1^q you choose, therefore, k is a function of p and q, so you cannot just set q = k+1 afterwards. I would choose 0^p1^{(p-1)!} for some p prime at least two greater than the pumping length, since then xy^0z = xz = 0^k1^{(p-1)!} for k<p. This is possibly not the most ... 3 For the record, there is a very simple proof using the Myhill–Nerode criterion. Let p_i be an enumeration of all primes. Since 0^{p_i} 1^{p_i} \notin L while 0^{p_j} 1^{p_i} \in L (for j \neq i), we see that the words 0^{p_i} are pairwise inequivalent with respect to L, and so L is not regular. If you really need to use the pumping lemma, let ... 0 HINT: Start with a DFA for the original language L, and modify it to get a DFA for the truncated language. The only part of it that you need to change is the set of acceptor (final) states. 0 I'm not sure this'll help, as I'm not very familiar with comp sci, but consider a general discrete example$$x_{k+1} = f(x_k), \quad k=0,1,...,n-1 \qquad (1.1)$$where f(x_k) determines the next state. Then consider a different discrete case where we have a input variable a_k so that the above becomes$$x_{k+1} = f(x_k,a_k), \quad k = 0,1,...,n-1 ...

0

This fact is absolutely obvious, and the intended induction proof is apt to make it less believable. Hear this: We are given a finite $\{a,b\}$-string. Interchanging all $a$s and $b$s, and then reversing it produces the same result as first reversing it and then interchanging all $a$s and $b$s.

0

Let us prove the result by induction on the length $|w|$ of $w$. If $|w| = 0$, then $w$ is the empty word and the result is trivially true. Suppose that the result holds for all words of length $\leqslant n$ and let $w$ be a word of length $n + 1$. Without loss of generality, we may assume that the last letter of $w$ is an $a$. Thus $w = va$ for some word ...

0

Do it as suggested by mrp but you have to make his automaton deterministic. This is easy, just add a new "dead" state and add transitions from the first 6 states to it with for the symbol that was not yet used on those states. This new state has transitions into itself for both a and b.

1

The language $L$ consists of all strings start start with an $a$, then five $b$'s, then any any number of $a$'s and $b$'s (including none) and four $b$'s at the end. Thus, a DFA that recognises $L$ can be described as follows. The start state only has an $a$-transition to the next state, and the following five states only have $b$-transitions to the next ...

0

Using the state diagram to regular expression algorithm outlined in section 9.2 of Tennents "Software Specification" I was able to come up with the following language. $b^*ab^*aaa^*b(a + bb^*a) + b^*ab^*abb^*a + b^*ab^*aaa^*b(a + bb^*) + b^*ab^*abb^*ab(a + bb^*a) + b^*ab^*abb^*a + b^*ab^*abb^*ab(a + bb^*)$ Verifying this with the diagram shows the language ...

0

There is a standard way to do this, though it is unlikely to give you the most efficient result. First create a non-deterministic finite automaton to recognise the finite language you want. This could consist of one "piece" like the one you have shown for each word - so, for your first question, three pieces: the states in the second would be labelled ...

0

To prove that a certain function is primitive recursive, as you probably know, you need to be able to describe the function using only the basic primitive recursive functions. This gives us a definition that could look like: $$\mathrm{floorlog}(b,x) = \left\{\begin{array}{ll} \mathrm{null}(x) & b = 0 \\ g(b-1, \mathrm{floorlog}(b-1, x), x) & b > ... 3 A DFA has no \epsilon-transitions, so this is not a DFA. I would rather called your automaton a nondeterministic finite automaton with \varepsilon-moves. Your regular expression 1(11 \cup 0^*)^* is correct. Your informal description is almost correct: you should just modify your sentence each 1 after the first, will be accompanied by at least ... 3 You can be pretty sure that your answer to (ii) is wrong, since (iii) asks you to show that aabbccc\in L(M), and aabbccc doesn’t satisfy the condition in your answer to (ii). Notice that there is only one possible transition from the initial state q_0, so any word that is accepted must start with a. When that a is read, the stack remains empty, ... 1 Property 2 is immediate from the definitions: L_{csl} is defined as the family of languages generated by a context-sensitive grammar. L_{cfl} is the family of languages generated by a context-free grammar. Every context-free grammar is trivially a context-sensitive grammar, because a context-free grammar is defined to be a context-sensitive grammar that ... 0 HINT: Stack amber plates as they arrive. When a blue plate comes in followed by a *c(hartreuse plate, unstack two amber plates. Throw a tantrum if the amber plates don’t arrive in pairs, or the blue and chartreuse plates don’t alternate properly. 1 Consider that, if you have a DFA which accepts words in L, then it can be in one of finitely many states after it reads the first letter - so, to test if a word is in L\ominus 1, we just start the DFA at each of the states it could be in after one letter and if it accepts when started in any of these, the word is in L\ominus 1 - and, if you know how to ... 1 Let$$ L_0 ={\{ c^n a^m b^p \mid n+m=p,p \geqslant 6}\} = {\{ c^n a^m b^{n+m} \mid n+m \geqslant 6}\} $$If L_0 was regular then,$$ L_1 = L \cap \{a,b\}^* = \{ a^m b^m \mid m \geqslant 6\} $$would also be regular (since \{a,b\}^* is regular and regular languages are closed under intersection). Similarly, since \{a^m b^m \mid m \leqslant 5\} is a ... 2 Let us choose w=a^mb^mc^{2m} with m is the number of states of your automaton, and apply the pumping lemma you will have: there exists x,y,z such that:$$\left\{\begin{matrix} w=xyz=a^mb^{m}c^{2m}& (1) & \\ |xy|\leq m& (2) & \\ |y|=d\geq 1& (3) & \\ xy^*z\in L_5& (4) & \\ \end{matrix}\right.$$The equations (1) ... 1 Hint: Split a^n into \color{blue}{a^n} and \color{green}{a^5}, that is, consider language$$L = \{\color{blue}{a^n}\color{green}{a^5}b^m \mid \color{blue}{n}\geq m, m > 0\}, where the two new letters $\color{blue}{a}$ and $\color{green}{a}$ are just two distinguishable letters $a$, and $\color{blue}{n} = n-5$. For the second language observe ...

3

Have you seen the proof of the pumping lemma? The rough outline goes like this: If $L$ is a regular language, it is accepted by some finite machine $M$ $M$ has some number of states, say $n$ If $L$ contains a string $w$ of $n$ or more symbols, then $M$, in accepting $w$, must go through more than $n$ states, and since it has only $n$, it must go through ...

0

Informally, the pumping lemma states that "In regular languages, every word that's at least length $n$ can be split into $xyz$ where $y$ can be repeated indefinitely." (Hence the "pumping", I presume.) The $|w| \geq n$ constraint simply takes care of the "at least length n" part. If you allowed $w$ to be any length, the pumping lemma wouldn't hold. ...

2

The $\epsilon$-transition $q_0 \to q_4$ from the (former) first automaton to the (former) second automaton would occur somewhere in the word $w$. So far the prefix $u$ of $w = uv$ was consumed, where $u \in L_1$ because $q_0$ is an accepting state of the first automaton. The suffix $v$ of $w$ is now available with the combined automaton at $q_4$ which is ...

1

As you observed, you get an OR relation by doing a disjoint sum, as in your diagram. To get an AND relation, you must take the product of the two automata. The product of $A$ and $B$ has states that are pairs of states, one from $A$ and one from $B$, so that it tracks the states of $A$ and $B$ together. Then it can accept if it is in a state $\langle ... 1 Given the hypothesis that$L$is infinite, I suspect that$L_1$and$L_2$are supposed to be infinite as well. You can actually use the pumping lemma to help you here. Let$p$be the pumping length for$L$, and let$w\in L$with$|w|\ge p$. Use the pumping lemma to decompose$w$as$w=xyz$, where$|y|\ge 1$, and$xy^kz\in L$for each$k\ge 0$, and let ... 0 Hint: Regular languages are closed under union, intersection, and complement. (see http://en.wikipedia.org/wiki/Regular_language#Closure_properties). So if your language$L$contains a string$s$, build a regular language that recognizes just$s$and also a regular language that recognizes$L \cap s^c$, i.e. all strings in$L$except$s$. 0 The first is ok, the second is more like : 4 Let me show you a systematic approach. Think of each of the state names as an abbreviation for a regular expression corresponding to the set of words that end at that state when starting from the initial state. Since$B$and$C$are the acceptor states, we want the expression$B+C$. (I’ll use$+$instead of a comma for or; I use$\lambda$for the empty ... 1 Your first conversion is correct. You need to label your initial node in your second automaton. You also need to consider the epsilon-closure when creating new states - e.g. {1,3} should not be a node, as it is possible to reach state 2, from state 1, under an epsilon-transition. 0 Let$A$be the alphabet. If$A = \{a,b\}$, then$n(a) + n(b)$is simply the length of the word. Therefore your language is the set of words of even length and$(AA)^*$is a simple regular expression for it. If$A$has more than two letters, then a regular expression for your language is$\bigl(C + (a+b)C^*(a+b)\bigr)^*$, where$C = A - \{a,b\}$. 0 Regular languages are closed under intersection and under left quotients$^*$. Therefore, if$Lwas regular, then the languages \begin{align} L_1 &= L \cap a^* = \{ a^k \mid k = 2^n + 273 \text{ for somen\$ }\} \\ L_2 &= (a^{273})^{-1}L_1 = \{ a^{2^n} \mid n \in \mathbb{N}\} \end{align} would be an infinite regular language. You can now ...

Top 50 recent answers are included