Tag Info

Hot answers tagged

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


1

I guess you mean regular languages accepted by finite automata. Just Google one of these words: finite automaton, DFA, NFA, regular language or look at this question How to convert finite automata to regular expressions? Edit. To answer your last remark, you might be interested in this paper, which heavily relies on Stone duality.


1

Note that if you look at the transition from $q_1$ with the symbol $0$, then it can go to $q_1$ as well by using the empty transition after passing through $q_0$ first. The DFA you've written down doesn't accept "00", which is accepted by the NFA above. You also need, as mentioned in the other answer, to make the start state $\{q_0, q_1\}$, since that ...


1

There are several problems here, though the choice of $s$ is sound. First, I suspect that you meant that $x=a^q$, though the $q$ is missing both in the definition of $x$ and later in the expansion of $xyyz$. In that case you might as well say that $x=a^{m-k}$. Next, the definition of $z$ is simply wrong: $z=bba^m$. Now the pumping lemma says that $xy^2z\in ...


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

Your idea goes in the right direction - you just need to also keep track of the fact that you essentially "skipped" an input in the non-chosen automaton. In a nutshell, what you want is a variant product construction: Let the original automata be $A_i=(Q_i,q_i^0,F_i,\delta_i)$ for $i=1,2$. Then your NFA has set of states $Q_1\times Q_2$, with initial state ...


1

As Rolf Hoyer noted in the comments, your DFA does not accept $aaab$, which is in $L$. The problem is that after you’ve read $a$, it really does make a different whether the next input is an $a$ or a $b$: if it’s an $a$, you can read any number of $a$s and still be two-thirds of the way to having the substring $aab$, but if it’s a $b$, then another $a$ puts ...


1

HINT: $L_1\cup L_2=L_2$, and $L_1\cap L_2=L_1$. For (d), note that you can design a DFA that handles the members of any finite collection of words, like $\{\lambda,ab,a^2b^2\}$, individually, and handles all other words separately. Your use of the pumping lemma in (a) is correct.


1

Your work for (a) is fine, but your regular expression is wrong: its last term matches $aaaaa$, for instance, which is not in $L$, and none of it matches $bab$, which is in $L$. It looks as if you tried to generate it from the transition graph and made quite a few mistakes; in particular, it looks as if you forgot to keep track of which states in the ...


1

With very minor variations your idea can be used to design a PDA that recognizes either of the languages $\{a^nb^mc^k:k\ge n+m\}$ and $\{a^nb^mc^k:k>n+m\}$, so these are both context-free. A similar idea also yields PDAs for $\{a^nb^mc^k:k>n\}$ and $\{a^nb^mc^k:k>m\}$. The problem with the language in your question is that while we can use the stack ...



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