# Tag Info

1

An element of $L'$ could potentially be a palindrome, but that does not rule out the possibility that $L'$ is regular. Some elements of the language $(\mathtt{a}+\mathtt{b})^\ast$ are palindromes—in fact it contains all possible palindromes—but the language is still regular. A theorem says that if language $X$ is regular, than $X^R$, containing all the ...

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

Hint : The acceptable string with minimum length is $ab$ (length $2$). Hence, it must have at least $2+1 =3$ states.

0

Showing that your context-free gramma produces only strings with an equal number of $a$'s and $b$'s is easy. You start out with the non-terminal symbol $S$. That contains zero $a$'s and zero $b$'s. Now apply one of the productions \begin{eqnarray} S &\to& aSbS \\ S &\to& bSaS \\ S &\to& \epsilon \end{eqnarray} Each production ...

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

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

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

Hint: Each word of $L_1 = (\mathtt{ab}^*)^*$ starts with $\mathtt{a}$ or is empty. All words of $L_2 = \mathtt{b}(\mathtt{a}+\mathtt{b})^*$ start with $\mathtt{b}$ and are non-empty. I hope this helps $\ddot\smile$

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.

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

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

When you have a regular language $\def\L{\mathscr L}\L$, the pumping lemma gives you a magic constant $p$, which in this case is at most 5, because you have an automaton for $\L$ that has 5 states. The magic constant has the property that if $s$ is any string in $\L$ that is at least $p$ characters long, then we can find arbitrarily long strings in $\L$ of a ...

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

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

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

0

My professor, when teaching us the pumping lemma for the first time, he introduced it as a game between two people. The goal for you is to prove that a language is not regular. Step 1: You choose some $p\in\mathbb{Z}$. So, $p$ is already an integer. You don't have to show this. It is by assumption. Step 2: Your opponent chooses some $w\in L$, with $|w|\geq ... 1 If by "NFA which is already deterministic" you mean an NFA that from each state and for each letter input it has only one choice to move, then the reachable states within the$2^Q$states of the equivalent DFA are exactly the singletons. 0 So one source tells you to consider strings$xuv^iwz$and another tells you to consider$uv^iw$. How is$xu$in the first different from$u$in the second decomposition? 0 convert it to a dfa and work from there. #itsduein85minutes 0 To apply the pumping lemma to show that some language$\mathscr L$is not regular, you play a game like this: Mr. Pumping Lemma gives you a pumping constant$p$. You pick a string$s$of length at least$p$. Mr. Pumping Lemma divides$s$into three parts$uvw$, subject to the restrictions that$|uv|\le p$,$|v|\ge 1$. You now "pump" the$v$part by picking ... 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

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.

0

There is a unique minimal DFA for a given language. To prove that a given DFA is minimal you have to prove that there are no unreachable states that can be eliminated and no nondistinguishable states that can be merged. Wikipedia gives algorithms and references to relevant papers for both in the article on DFA minimization.

0

I would suggest two ways: Perform minimization (perhaps by a computer) and show the number of states is the same. Check that all states are reachable and distinguishable, i.e. For any state $s$ there is a word $w \in \Sigma^*$ such that $q_0 \xrightarrow{w} s$. For each pair $(s_1,s_2)$ of states present a word $w \in \Sigma^*$ such that for $s_1 ... 0 Question:Consider the language L expressed by (a+b)*a defined over Σ = {a, b}. Draw FA and construct the CFG corresponding to the language L. Solution: (a+b)*a 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$. 0 Using subset notation is not essential. If you can give a clear proof using mainly words, that is often better than a highly technical algebraic proof. To prove that${\rm LHS}\subseteq{\rm RHS}$I would suggest something like this. Let$w$be a word which matches$(r\cup \varepsilon)^*$. Then by definition$w$can be written $$w=w_1w_2\cdots w_n\ ,$$ ... 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 ... 0 The usual method constructs an automaton that has only one state. Initially, the stack has the nonterminal$\def\nt#1{\langle{#1}\rangle}\def\ntt#1{\nt{\text{#1}}}\ntt{expr}$on it. At each step the automaton should look at the top stack element. If it is a nonterminal, the automaton should remove it and replace it with its definition from the grammar. ... 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 ... 0 I don't know if you were asked to use necessarily the pumping lemma in order to solve the problem, but in this case of language, it is much easier to use Parikh's theorem. The alphabet of the language is$\Sigma=\{a\}$. So, for every word$w$, Parikh's vector is$P(w)=|w|_{a}$(which is the number of occurences of$a$in$w$). Then, the set of Parikh's ... 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 ... 0 Imagine a Turing machine that has C cells that each can have S possible states. The number of states in the entire Turing machine is equal to$S^C$. If the Turing machine has an infinite number of cells, the Turing machine has$S^\infty$states, which is equal to$\infty$. 2 i am new here this is why i don't know how to post or where to write.sorry i bother you but i just want to match my answer because i was not sure about my answer. thank you for answer. 2 A context free grammar corresponding to the language$L\$ is: $$S \to aS|bS|a$$

Top 50 recent answers are included