Tag Info

New answers tagged

2

For b), let $L_1=\Sigma^{*}$ and let $L_2$ be any non-regular language you like that contains the empty string. Then $L_1 L_2=\Sigma^{*}$. For a), let $L_2$ be the set of all strings not of the form $a^n b^n$ for $n\ge 1$. (This is clearly non-regular because its complement is non-regular.) Every string is either not of the form $a^n b^n$, or is of that ...


0

Neither of your arguments works. When you use the pumping lemma, you are not allowed to specify $u,v,x,y$, and $z$: all you know is that if $s$ is a word in the language that is at least as long as the pumping length $p$, then $s$ has some decomposition $s=uvxyz$ such that $|vxy|\le p$, $|vy|\ge 1$, and $uv^kxy^kz$ is in the language for each $k\ge 0$. ...


2

Recursively enumerable sets are closed under union, but not complementation; this is true. So the argument "take the complement of the union of the complements" does not show that the recursively enumerable sets are closed under intersection. However, just because one argument doesn't work, doesn't mean the principle is false. Indeed, recursively ...


0

Well, I don´t knew if you knew it, but the intersection of an regular Language with an other one is regular. And every finite language is regular (proof: build an DFA). If you now intertersect an finite with an infinite: Let´s look at the Intersection Property - In your finalSet will be only values, which were in BOTH Sets. -> So the size of the final Set ...


1

$\{a^nb^m:m,n\ge 0\}$ is a regular language, but it is clearly not finite. It contains one word for each ordered pair $\langle m,n\rangle\in\Bbb N\times\Bbb N$, so it has the same cardinality as the set $\Bbb N\times\Bbb N$ and is therefore countably infinite. Every finite language is regular, but there are many regular languages that are not finite. Indeed, ...


0

I think for acceptance the expression is $(a\cup b)^*b(a\cup b)$. You don't need to read something before the last $b$ but one. (for example $ba$ is accepted by your machine). For the halting and reject notice that you cannot halt in $q$ nor in $v$ since you can read anything from there. Hence the only possibility to halt and reject are: be in $r$ and ...


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


0

The statement that you paraphrased is inaccurate, since there are obviously DFAs with $i_L$ states that do not recognize $L$. What the authors meant is this: In the proof of [the Myhill-Nerode theorem] it is established that if $L$ is a regular language, and the index of $\sim_L$ is $i_L\in\Bbb N$, then it is necessary for a DFA to have at least $i_L$ ...


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


0

Your DFA recognizes the strings that contain $10$ somewhere as a substring. You want to recognize only those that end in $10$ (though they may of course have other $10$ substrings internally). You need to change the transitions out of $s_2$. If you’re in $s_2$ and get any more input, you’re essentially starting over as if you were in $s_0$ getting the very ...


0

It’s not quite right: the only word that puts the automaton in state $s_0$ is $\epsilon$, the empty word, and the only words that put the automaton in state $s_1$ are those of the form $01^*$. Thus, the desired regular expression is $01^*+\epsilon$ (or $01^*\cup\epsilon$, if you use that version of the notation). Any string that starts with $1$ ends up ...


0

First of all, a small correction. The language accepted by the automaton in Figure 4.1 is $$ L_1 = \{a^nb^m \mid n \geqslant 1, m \geqslant 0 \} \cup \{ba\} = a^+b^* \cup \{ba\} $$ Now, if $L_2 = b^*$, then $$ L_1/L_2 = \{ u \in A^* \mid \text{there exists $n \geqslant 0$ such that $ub^n \in L_1$} \} $$ I claim that $L_1/L_2 = L_1$. Indeed, if $u \in L_1$, ...


0

Number of a <= number of b, and Number of b <= 2* number of a Assume that the input string is aaabbbbb For every a Mark a as A If there is b, mark it as B. Else reject // j<i for example AAAaBB End for If there is no unmarked b, accept //i=j, AAABBBbb now For every b Mark b as B Ifthere is an A, mark it as F Else reject. //j>= 2i, for example ...


0

Roughly: Given $M$ and input $w$ write a new machine $f(M,w)$ that clears out the tape, then writes $w$ on the tape, then runs $M$. So this machine ignores its input. Then $(M,w)\in HALT$ if and only if $f(M,w)\not\in LOOP$.


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


0

If lambda is the empty string then that isn't correct. Remember the start state is the epsilon closure of the start state - in other words the start state should be the union of q0 and q1 *note I havent done NFA to DFA in awhile so correct me if im wrong.


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.


0

I have difficulties reading your answer from the image, but the DFA looks fine, while the regexp does not. Counter example: $ba$ seems not to be recognized.


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

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

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

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


0

In regular expressions there can be two meanings for the '+'. First, it can be the 'Kleene' '+' that stands for several times and at least once. But when this is the case its superscript: For example $a^+$ stands for $\{a^n|n\geq 1\}$. Otherwise it can stand for 'or'. in that case it's not superscript. For example $a+b$ stand for either $a$ or $b$. For ...


0

Directed algebraic topology is a field of algebraic topology with applications towards in particular semaphores and deadlock detection. See e.g. Raussen.


0

My answer to this problem on a recent homework was originally similar to the other answer on this question: Perform a breadth first search on the input, If a non-accept state is visited reject, Otherwise accept. However, this solution is wrong. This decider will accept a DFA that does not accept all inputs if, for example, there is no transition for one of ...



Top 50 recent answers are included