# Tag Info

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 ...

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$: $$... 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 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 ... 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, ... 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 ... 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 ... 2 You want all the words on \{a,b\} that cannot be split in three equal sub-word. There is two possible case either the length of word is a multiple of 3 or it is and there is some index where the letters differ. The first case is easy you just have to ensure that you don't generate multiple of 3 letters (hence generate all the multiple of 3 possible and ... 2 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 ... 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 ... 1 Machine M1 is more powerful than machine M2 if, intuitively, anything that M2 can do, M1 can do as well. Formally, M1 is more powerful than M2 if, given any specification of a problem and a solution of it on M2, there exists a solution of the same problem on M1. One may further demand that the complexity (either time or space) does not ... 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 ... 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 ... 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.

1

According to this page, there are 788,258 words in the Bible but only 14,565 distinct words. Now, it is shown in [1] that a full Scrabble lexicon with 94,240 entries can be represented be a DFA with 19,853 states. So you can expect the DFA of the Bible to have roughly $19,853 \times \frac{14,565}{94,240} \approx 3068$ states. [1] A. W. Appel et G. J. ...

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

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 ...

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