# Tag Info

2

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

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

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 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 ... 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' ... 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 We don’t actually count the 0s and 1s: 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, ... 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 You can write down a recurrence to solve this: If a_n means the set of strings of length n in the language, then we have$$ a_n=a_{n-2}+a_{n-3}, \qquad a_0=1, a_1=0, a_2=1 $$Fully solving the recurrence would be overkill when all you're interested in is finding a_{10}, but it should be fairly quick to compute a_3, a_4, \ldots, a_8 and then a_{10}. ... 1 We could also associate a geometric series with$$(bb+aab)^\star=\varepsilon+(bb+abb)+(bb+abb)^2+\ldots Since each word in this language is uniquely identified by the occurrences of $bb$ and $aab$ parts and since we are only interested in the length of the substrings $bb$ and $aab$, we consider the series \begin{align*} ...

1

HINT: Palindromes are easy: build them from the middle out. You can get all of them of even length with the productions $S\to\lambda\mid 0S0\mid 1S1$; you’ll have to work just a little harder to get the ones of odd length. (I use $\lambda$ for the empty word; many people use $\varepsilon$.) Your second language is the union of two simpler languages: ...

1

HINT You are close. Think about how many times you need to see a 1 to make it all the way from $S_0$ back to $S_0$. To make a regular expression describing the language, write an expression for going one time around the entire thing, and then take abitrary powers of that.

1

Look at the construction: each set of states in the NFA becomes a single state in the DFA. A set of $n$ states has $2^n$ subsets, so if the NFA has $n$ states, the DFA will automatically have $2^n$ states, one for each subset of the state set of the NFA.

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

1

Use closure properties of regular languages. Define the new alphabet $\Gamma = \Sigma \cup \{\chi\}$, where $\chi \notin \Sigma$. The languages $L_a = \{a, \chi\}$ are finite, thus regular. So the substitution defined by $s(a) = L_a$ applied to your language $L$ gives a regular language. Intersecting that with $((a \mid b \mid \ldots) \chi)^*$ gives a ...

1

Let $p$ be a prime number greater than the pumping length, and try $0^{p-1}1^p$. Show that when you pump up, you get something of the form $0^{p-1+kr}1^p$ for some $r$ such that $1\le r<p$, and show that there is a $k\ge 1$ such that $kr-1$ is a multiple of $p$, i.e., such that $kr\equiv 1\pmod p$.

1

$L=L_1\cap L_2=\left \{ c \right \}$, so $L$ is regular.

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.

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