# Tag Info

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

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

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

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

2

You're almost correct: not quite, because your language accepts the empty string :) The original is correct. If you used + (one or more) rather than outermost * (zero or more), then the languages denoted by the two REs (yours, with that change, and the original) are the same language. Let's alter your RE as mentioned:$$(a(a+b)^*b)^+ + (b(a+b)^*a)^+ ... 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}\;,\\ ...

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

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

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

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

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 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. 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 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 ... 1 The second grammar can generate epsilon whereas the first one can not, so they are not equivalent. Since epsilon is not in L, only the first grammar generates L. 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 ... 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 ... 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

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

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

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

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