# Tag Info

2

Any non-empty string winds up in Q2 and stays there, so you match more than you should. For example, $bbb$ is accepted even though it's not in $L$. The initial state should keep reading input until $a$ is read, and the other one should be the accepting state and just consume the rest of the input by looping any input to itself.

1

$L_1\cup L_2=\{a^mb^n:m,n\ge 1\}$, which corresponds to the regular expression $aa^*bb^*$ and is therefore certainly regular, but your DFA isn’t quite right: it accepts the language corresponding to the regular expression $a^*bb^*$, i.e., $\{a^mb^n:m\ge 0\text{ and }n\ge 1\}$. You can fix it by introducing a fourth state $q_0$, making $q_0$ the initial state ...

0

To see that $L$ is regular, consider the DFA $M=(Q,\Sigma, \delta, q_0, F)$ where $Q=\{0,1,2\}$, $\Sigma=\{a\}$, $q_0=0$, $F=\{1,2\}$, and transition function $$\delta(n,a) = \delta(n+1,a),$$ with $n\bmod 3$, or equivalently, the regular expression $$(a\cup aa)(aaa)^*.$$

0

Let us first prove that REG is not RE. I will use the book Introduction to Automata Theory, Languages and Computation by Hopcroft and Ullman. $\newcommand{\S}{\mathcal S}$ Let $\S \subset RE$ a set of recursive languages, and $L_{\S} = \{ <M>, L(M) \in \S \}$ ($<M>$ denotes here the an encoding of the TM M, so that we clearly define $L_{\S}$ as ...

1

Assuming your alphabet $\Sigma$ includes $a$ (if $a$ is an arbitrary word in $\Sigma^*$, then the proof is completely analogous to the method here but a bit fiddlier), the pumping lemma implies that for some $n\geq 0$ and $m > 0$, we have $a^{n + tm}\in L$ for all $t > 0$. But this is clearly false; take $t = n$, for example.

1

Like you said, we have $5 |w| = 3 |u|$. Since $3$ and $5$ are co-prime, $|w|$ is a multiple of $3$. Therefore, there exist $w_1, w_2, w_3\in \Sigma^*$ such that $|w_1|=|w_2|=|w_3|$ and $w=w_1 w_2 w_3$. Now we have : $$\begin{array}{c c c c c} w^5&=&(w_1 w_2 w_3)(w_1 w_2 w_3)(w_1 w_2 w_3)(w_1 w_2 w_3)(w_1 w_2 w_3)& & \\ &=&(w_1 w_2 ... 1 You can in fact use the pumping lemma to prove that the language L=\{a^p:p \text{ is prime}\} is not regular: As a reminder and clarification of notation: The pumping lemma states that any word w\in L with |w|>n for a specific n can be split into three parts w=abc so that: |ab|\leq n |b|>0 \forall i\in \mathbb{N}:ab^ic\in L Suppose ... 0 I'm a noob at automata. As, far as I know, there is no unique solution for a conversion from DFA to NFA. Therefore, your answer is not challengeable. Although, you can try and make the tightest possible state diagram. Whereas, when you are converting an NFA to DFA , you will find a unique solution. 1 Your first langauge is :$$A = \{xy | x,y \in \{a,b\}^*,\#a(x)=\#b(y) \}$$Which means number of a's in x is equivalent to number of b's in y; where x\in\{a,b\}^* and y\in\{a,b\}^*. Therefore, xy = \{a,b\}^*\{a,b\}^*= \{a,b\}^* A = \{w\mid \#_a(w)=\#_b(w)\} is not regular. CFG for A$$S → aSbS | bSaS |\in $$Your second langauge is :$$B ...

1

Let $M=(Q,\Sigma, \delta, q_0, F)$ where the set of states is $$Q=\{q_0, q_1, q_{11}, q_{10}, q_f\},$$ the input alphabet is $$\Sigma = \{0,1\},$$ the transition function $\delta: Q\times \Sigma\to\ Q$ is defined by \begin{array}{c|c|c|c|c|c} \delta(q,b)& q_0 & q_1 & q_{11} & q_{10} & q_f\\\hline 0 & q_0 & q_{10} & q_f ...

1

Here is a NFA accepting your language, where I the an initial state, and F is a final state. It reads the word, and, in a non-deterministic way, choses to read one of the subword you want. Then, you "just" have to determinise it (be careful, it can have up to $2^8$ states… you may want to rewrite the NFA with less states)

1

Possible solution: Build a DFA $A_1$ that accepts strings with $100$. Build a DFA $A_2$ that accepts strings with $110$. Build DFA $A$ that accepts strings with $100$ or $110$. The latter is the union of DFA's $A_1$ and $A_2$ (the union accepts a string iff it is accepted by $A_1$ or $A_2$). Here [ link ] (pp.3-5) you can find some example how to perform ...

0

HINT: Have a non-terminal symbol $X$ that generates words of the form $a^mXa^m$ for $m\ge 0$ and then turns into $Yc$. Then have $Y$ generate words of the form $a^nb^n$ for $n\ge 0$. The end result will be words of the form $a^{m+n}b^nca^m$.

1

There are mechanical techniques for converting a regular grammar to a regular expression for the language; for context-free grammars, however, I know of no algorithmic approach. In this case, however, the nature of the grammar makes a rigorous analysis fairly straightforward. Notice that if you use the production $S\to AA$ in a derivation, you can never get ...

2

A derivation may start by using the production $S\to aS$ any number of times, but eventually it must use the production $S\to A$, since the only terminal production is $A\to\epsilon$. Say it uses $S\to aS$ $n$ times, where $n\ge 0$, and then $S\to A$; at that point we have $a^nA$. Now consider what kinds of strings can be produced starting with $A$. The ...

1

The language of this grammar is the one given by any string that has the following structure. The string $s = s_+ s_-$ is divided into the prefix $s_+$ and the postfix $s_-$. The prefix consists of an arbitrary number (possibly zero) of $a$'s. Let $n$ be the length of $s_-$, so that we can write $$s_- = s_1 s_2 \dots s_n$$ and note that $n$ must be an even ...

2

You have the right idea, but you need to be more careful to make all of the new states different. For each $p=\langle q,w\rangle\in P$ and each $k\in\{1,\ldots,|w|-1\}$ you want to add a new state $q_{p,k}$, and if $w=a_1\ldots a_{|w|}$ you also want transitions \begin{align*} &q\overset{a_1}\longrightarrow q_{p,1}\;,\\ ... 0 Ok, I think I figured it out: M=<Q,Σ,δ,s,A>. so for M' (which will be an NFA): Q'=Q\A ∪ {q'|q∈Q}, s'=s, A'={q'|q∈A} now the transition function ∆: let it be q∈Q, a∈Σ. lets mark q_r=δ(q,a) (q_r∈Q). so for every (q,a), so that q∈Q, a∈Σ the definition for ∆ will be: ∆(q,a)= δ(q,a)=q_r ∆(q',a)=q'_r ∆(q,a')=q'_r , whereas a'≠a. ... 1 HINT: Start with a DFA M_0=\langle Q,\Sigma,\delta_0,s,A\rangle that accepts L. Now modify M_0 to get a FFA M=\langle Q,\Sigma,P,\delta,s,A\rangle that is essentially identical to M_0 in its operation. Use \delta_0 to define both P and \delta. 0 Suppose \Sigma = \left \{0,1 \right \}. Let M' be a NFA such it has two copy of states of M like Q_1 and Q_2. Now if q_i\in A for DFA M, then q_i^2\in A'and :\delta(q_i,\sigma)=q_j \Rightarrow \delta '(q^2_i,\sigma)=\left \{ q^2_j \right \}$$Let \delta (q_i,0)=q_j and \delta (q_i,1)=q_r then:$$\delta '(q^1_i,0)=\left \{ ...

1

We don’t actually count the $0$s and $1$s: we just keep track of the difference. The difference $n_0(s')-n_1(s')$ increases by $1$ every time we read a $0$ and decreases by $1$ every time we read a $1$. If the difference is always in the set $\{-2,-1,0,1,2\}$, we want to accept the string, and if it ever goes outside that set, we want to reject the string, ...

2

How about $L_1=\{\mathtt a^n\mid n\text{ is prime}\}$ and $L_2=\{\mathtt a^n\mid n\text{ is composite}\}$?

1

Consider the automata that decide $L_1$ and $L_2$, $DFA_1 = (Q_1,\Sigma,\delta_1,q_{s1}, F_1)$ and $DPDA_1 = (Q,\Sigma,\Gamma, \delta_2,q_{s2},Z,F_2)$. We assume that they are defined over the same alphabet. We can construct the intersection of the two automata as follows. Let $DPDA_{L1\cup L2} = (Q_3,\Sigma,\Gamma, \delta_3,q_{s3},Z,F_3)$. Where $Q_3 = ... 1 Let$A = (\delta_A, Q, q_0, F)$be a DFA for$L$(in some alphabet$\Sigma$). Then define$B$as follows: The states$Q_B$of$B$are of the form$[q,S]$where$q \in Q$and$S \subseteq Q$. The initial state of$B$is$[q_0, F]$.$\delta_B([q,S],a) = [\delta_A(q,a), T]$where$T = \{p \in Q: \exists b \in \Sigma: \exists p' \in S: \delta_A(p,b) = p' ...

2

Given any TM $M$, construct a TM $M'$ which is the same as $M$ except that the only time it will print something is just before halting. Then if I can decide the "printing problem", I can run my decision procedure on $M'$ and I have decided the halting problem on $M$.

2

$A^*$ is the set of finite strings of elements of $A$. $2^{A^*}$ is the set of all subsets of $A^*$, that is, the set of all languages. This is vastly larger. For example, the following are elements of $2^{A^*}$: The set of all strings of length $1$. The set of all strings not containing some fixed element $a\in A$. The set of all strings in which every ...

0

We can show that $A^*\cong\mathbb N$ through a Gödel encoding of the indices of the letters of the alphabet. From this it follows that $P(A^*) \cong P(\mathbb N)$. So, for any alphabet $A$, $A^*$ is countable, while $2^{A^*}$ is uncountable. You will have to be more specific if you want a more specific answer. I'd like to take this time to address ...

1

Since, CFLs are not closed under complement property, while CSLs are closed under complement property. Every CFL is CSL , every CSL is recursive, and every recursive language is recursive enumerable language. So, complement of a CFL may not be CFL but that will be CSL sure, means, recursive as well as recursive enumerable language. Reference@wiki Edit : ...

1

The Game of Life is but one example of: Cellular Automata, which are very useful for modelling complicated, non-linear, systems in physics, chemistry, biology, meteorology, cosmology, computational science, engineering, .... the whole gamut. Such stable patterns will arise, but are very difficult to predict from the basic laws. Cellular automata are ...

0

Yes this can language can be proven not regular using the pumping lemma. The strongest statement of the pumping lemma will work: if $L$ is regular, then there is a $p$ (equal to the number of states in a DFA accepting $L$), such that for any string $s\in L$, any substring $r$ of $s$ of length $\ge p$ has substrings that can be pumped. The proof is the same: ...

1

Defining $s$ partly in terms of $p$ is an easy way to ensure that $|s|\ge p$; this is necessary if we are to apply the pumping lemma. It also gives us some control over what the part $xy$ of the $xyz$ decomposition will look like. Here I would start with an $s$ that just barely satisfies the condition putting it in $A$: $s=0^p10^{p-1}$. If $A$ were regular, ...

1

Remember that $s = 0^p1^p = xyz$. Now, if $|xy| \leqslant p$, then $xy$ is a prefix of $0^p$ and hence consists only of $0$s. Now, $y$ being a suffix of $xy$, it also consists only of $0$'s. Therefore, denoting by $|u|_0$ ($|u|_1$) the number of $0$s ($1$s) in a word $u$, one gets $|y|_0 = |y|$ and $|y|_1 = 0$, whence $$|xyz|_0 = |s|_0 = p = |s|_1 = |xyz|_1 ... 1 If s\in L, then s = a^ib^jc^k for some i,j,k\ge 0, but also s = a^mb^mca^nb^m for some m, n\ge 0. So we must have k = 1, and n=0. Furthermore, we must have i=j=m. So s = a^mb^mc = a^mb^mcb^m. But then we have to have m = 0. So s = c. Thus L = \{c\} is regular. 1 L=L_1\cap L_2=\left \{ c \right \}, so L is regular. 0 You need to construct three different regular expressions that generate exactly the sentences described. For (a), the following regular expression will do:$$c(cc)^*$$This regular expression says that there must be at least one c, so this takes care of the case where the number of c's is 1, and then we can add two c's as many times as we want, to ... 1 There are only countable DFA's but non countable number of languages, thus there is some countable infinite language which is not regular. Write that language as the union of the singletons of the words in the language 2 The Myhill-Nerode Theorem says that a language L is regular if and only if the number of equivalences classes of the relation R_L is finite, where$$ x R_L y \iff x, y \text{ have no distinguishing extension.}  (Terminology and notation are as in the article you cite.) In the case of $0^*1^*$, it's not hard to show that the equivalence classes are: ...

1

IF $L$ is a CFL, the Pumping Lemma for CFLs tells us that for some integer $n \ge 1$, if $s \in L$ and $|s| \ge n$, then $s$ can be written as $s = uvwxy$ where $|vwx| \le n$, $v\neq \varepsilon$ or $x \neq \varepsilon$, and for all $k\ge 0, uv^kwx^ky \in L$. If some $s\in L$ has length $n \le |s| < 2n$, then $L$ is infinite: for some $u,v,w,x,y$ ...

1

Note that $w\in L$ if and only if $w$ starts with a sequence of zeros followed by a sequence of ones (the length of each sequence can be zero). So to build a DFA for the language you can check: If the first letter in $w$ is $1$ then all of $w$ must be ones If the first letter in $w$ is $0$ then after we see the letter $1$ we must have all the letters $1$ ...

0

Look at the minimal DFA for $(01)^*$: it has two states, so any non-empty word of the language must cause it to repeat a state and therefore can be pumped. The minimum length of a non-empty word of the language is $2$, so the minimum pumping length is at most $2$. Note, though, that the language contains no word of length $1$, so if $w$ is in the language, ...

0

HINT: You can use the pumping lemma for regular languages. Suppose that $L_1$ is regular, and let $p$ be the pumping length. Let $w=0^p110^p$; clearly $w\in L_1$. The pumping lemma says that $w$ can be decomposed as $w=xyz$, where $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in L_1$ for each $k\ge 0$. We don’t know exactly what $x,y$, and $z$ are, but since ...

Top 50 recent answers are included