# Tag Info

8

I understand where they got baa and ab but how did they get it to have abb ? Just follow the arrows. "a" takes you to q1, then "b" takes you to q2, and another "b" takes you to q3, which is an accepting state. this is confusing to me with having a q7 state here. The q7 represents a failure state. Once the automaton enters that, it can't leave, so ...

4

Expanding on Newb's point, you can think of Q7 as a 'trap' - the automaton can never escape, since both A and B lead back to Q7. It is necessary so that all strings are valid inputs to the FA, acting as a 'catch-all' for strings longer than four characters; however, as we've noted before, only ab, abb, and baa will be accepted.

4

You could cheat. If $L$ is regular, then its complement (in the regular language given by $a^* b^*$) is also regular. That complement is $\{ a^k b^k \mid k \geq 0 \}$ and you can show that is non-regular using the pumping lemma. To totally avoid the pumping lemma, you could use the Myhill-Nerode Theorem; I'm paraphrasing the formulation below from ...

3

This is a funny question, and the answer is: it depends. First, if $x$, $y$ and $z$ are given sequentially, then pumping lemma implies that triplet $\langle 1(0^n),0,1(0^m)\rangle$ would have to be accepted for multiple values of $m$ and $n$, not necessarily equal. On the other hand, if the numbers are given simultaneously (e.g. on three tapes, or perhaps ...

2

The definition of $A$ is misleading. There is no reason to ever have $k>1$. Think of it as $$A=\{1y|y\in\{0,1\}^\star\textrm{ and }y\textrm{ contains at least one }1\}$$ The question from the commments is why does the regular expression equal this. There are many ways to express a string that contains at least one 1. $(0\cup 1)^\star10^\star$ is one ...

2

To show that these two expressions are equivalent, you must show how to translate from one to the other. Start with a string in $(a\cup b)^*b(a\cup b)^*$. There are two cases: Either the substring consisting of the first $(a\cup b)^*$ contains a $b$, or it doesn't. If the substring doesn't contain a $b$, then the string you started with is already in ...

2

Here's another approach via proof-by-contradiction. Assume for the sake of contradiction that $L$ was regular. Then, there must be a DFA that accepts the language. Let $n$ be the number of states this DFA has. Now, consider the first $n+1$ strings of the following sequence: $$a, aa, aaa, aaaa, ...$$ By the pigeonhole principle, we know there exist two of ...

2

There is a non-regular language that is recognized by a Turing machine. Yes, see the Chomsky hierarchy for more details. A Turing machine can have infinitely many states. It depends on what "states" mean: Turing machine can be represented by a graph which nodes are called states$^1$ and edges are called transitions. Here, this graph has to be ...

1

How about the following: I show that the automata has to differentiate between 3 different words that don't belong in the same state class. $w \in \{a,b\}^*$ $w_1 = \epsilon\\ w_2 = ab\\ w_3 = a$ For $w_1$ and $w_2$: \begin{align*} z_{12} = \epsilon &\Rightarrow& w_1z_{12}&=\epsilon \not\in L\\ &&w_2z_{12}&=ab \in L\end{align*} ...

1

No the proof is not correct. The function witnessing $A\leq B$ and the one witnessing $B\in RE$ have no reason to be the same. Also none of these two functions have any reason to be inversible (so your $f^{-1}$ does not exist). Here is a proof: Assume $A\leq B$, witnessed by a computable function $f:\Sigma_A^*\to\Sigma_B^*$ with $x\in A\Leftrightarrow ... 1 Start by defining a proposition$P(n)$for string length$n$. In this case,$P(n)$could be "No string in$L(G)$of length$n$has$ba$as a substring". As is often case, the base case$P(1)$is easy to prove. To complete the induction, you need to prove$P(n+1)$given$P(n)$for arbitrary$n \geq 1$. Let$T$be a string of length$n+1$for some$n$. ... 1 If$R$is a regular expression representing a language$L$, then the language$L'$of strict prefixes of$R$is also regular (exercise: build a regular expression or an automaton for it), and then checking$L'\cap L=\emptyset$is decidable, and answers the question whether$L$is prefix-free. 1 Better use a diagram when designing automata, writing out the tables soon gets too hairy. In this case, what your NFA has to "remember" is what the last (up to)$n$symbols where, and accepting states will be those where the "memory" is$n$symbols long and starts with 1. The "up to" above is to start filling the pipe (read symbols up to the$n$-th). Tables ... 1 The automata you have drawn are correct, but they are redundant. I would suggest, for a language that accepts only the empty string, a single state which is initial and accepting is enough. No other states or edges needed. For the language that accespts$a^*$, you draw a state which is initial and accepting and you also need a looping edge for$a$. 1 Your question is rather imprecise, but it makes it even more interesting... First, why is your question imprecise? Mainly because you not specify the alphabet and the coding of the triples$(x,y,z)$. So let me modify your question as follows: Is there an encoding of the triples of integers$(x, y, z)$on a suitable alphabet$A$such that the set$L$... 1 No. Say your numbers are written in base$b$, so your alphabet is symbols 0 to$b - 1$, and (,). The proof is standard pumping lema: suppose$L$is regular, let$N$be the pumping lema constant. Take$\sigma =(10^N,10^N,20^N)$. The pumping lema tells you that a piece of the first number can be repeated without touching the other two. But doing so makes ... 1 You can show that a language,$L$, is regular with one of those: Express the language with a regex Make an NFA that recognizes$L$Make a DFA that recognizes$L$Determine a primitive recursive function$f:\Sigma^*\to\{0,1\}$with the property $$f(x)=\begin{cases}1\text{, if } x\in L \\0\text{, else}\end{cases}$$ where$\Sigma$is the alphabet of the ... 1 There is an algorithm for converting a context free grammar to pushdown automaton. It only has one state and the stack symbols are$\{terminals\}\cup\{nonterminals\}\$ see for example: http://www.cs.uiuc.edu/class/fa05/cs475/Lectures/new/bwlec12.pdf (Don't really know if that is good source, I just googled and glanced at it, (where I learned this stuff ...

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