Tag Info

Hot answers tagged

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 $a$s 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 $b$s and then $4k+1$ number of $b$s 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