The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

5

Let me solve a simpler question first. Suppose we'd like to know If $C$ is context-free, must $F(C)=\{w: ww \in C\}$ be context-free? The answer is no: $F(\{a^i b^i c^j a^j b^k c^k\})=\{a^i b^i c^i\}$. As for the original problem, consider the context-free language that contains words of the form $\{a^i b^i c^j d a^j b^k c^k d\}$ or those which don't ...

4

Clearly not. Let $A=\{a\}$ and $B=\{aa\}$. Now, $A\cap B = \emptyset$ so $(A\cap B)^* = \{\epsilon\}$ but $A^*\cap B^*=B^*=\{a^{2i} : i \in \mathbb{N}\}$ (all strings consisting of an even number of $a$).

3

It seems you have hit the reasoning correctly: A set $S$ is a subset of another set $A$ if $w\in S\implies w\in A$. Since you are trying to show that $\forall w \in A^+ \implies w \in A^*$, you are proving that $A^+ \subseteq A^*$. One more legant way to formally do this is by finding a bijection between the two sets. Since $|A^*|$ = $|\Bbb N|$ you need to ...

3

You can always use the current state of the automaton to remember the last three characters you've seen. Now, you can implement two phases. In the first phase, you're happy if you're ever in the situation where the last three characters were $010$. In the second phase, you become unhappy if you ever see $010$ again.

3

If $\varepsilon \in L$, then necessarily $\varepsilon \in L^+$ (and the converse as well). This is because $L$ itself is contained in $L^+$ and $L^+$ is defined as the union over the powers $L^i$ of $L$ for $i \in \mathbb{N}_+$. Note $L^+$ is not defined as $L^\ast \setminus \{ \varepsilon \}$; this is a common mistake. Hence, $\varepsilon \not\in L^+$ ...

2

Given a language $L$, let $L_0 = \{\epsilon\}$ and, for $i\geq 1$, let $L_i = \{w_1\circ \dots\circ w_i \mid w_j\in L \text{ for each } j\}$, where $\circ$ denotes concatenation. Then the Kleene closure of $L$ is the language $L^* = \bigcup_{i\geq 0} L_i$.

2

What you have written (i.e., $\{ \varepsilon, 01, 0011, 000111, \ldots \}$) is simply $A$ itself. (Assuming $A^\ast$ is the Kleene star operation) you cannot prove $A = A^\ast$ because it is not correct. The Kleene star $A^\ast$ is defined as the union of the powers $A^i$, where $A^0 = \{ \varepsilon \}$ and $A^{i+1} = A^i \cdot A = \{ w \cdot w' \mid w \... 2 Your language could be simplified as follows, using$\emptyset^* =\{\epsilon\}: \begin{align*} L(\emptyset\emptyset^*+\emptyset) &=L( \emptyset . \{\epsilon\} + \emptyset) \\ &=L(\emptyset +\emptyset) & (\emptyset.\{\epsilon\}=\emptyset) \\ &=L(\emptyset) & (\emptyset + \emptyset = \emptyset) \end{align*} So the language L ... 2 Here's a hint; your language is, more or less, the concatenation of three languages: the strings not containing 010, the language consisting of the single string 010, and the strings not containing 010. Can you make a DFA which accepts all and only those strings not containing 010, perhaps as the complement of something? When I said "more or less" above, I ... 2 The "x\in A^{+}$. By definition$x\in A^{+} \wedge x\in A^{*}$for all$x\neq A^{0}$" is a bit weird. Not even from a computer science point of view but from a set theory or general mathematical point of view. First, you're saying the same thing again with "$x\in A^{+}$" which you shouldn't. Then, you're saying$x\in A^{*}$which is the desired result. I ... 1 The lexicographic order is defined on words, not on regular expressions. An interesting exercise is to describe the restriction of the lexicographic order to the language$a^*b^*$, assuming that$a < b$. Note for instance that$1 < a < a^2 < \dotsm < a^n < \dotsm$, but$\dotsm <a^nb <\dotsm <a^2b < ab < b$. 1$ printf "ab\n" | sed -En 's/b*// p' | od -t c 0000000 a b \n 0000003 This regex expression "$b*$" does match the empty string, which is zero '$b$', at the very front of the input "$ab$". This is in accordance with the definition of Kleene star since $b^*$ stands for the language $\{\epsilon, b, bb, \cdots\}$, where $\epsilon$ stands for the empty ...

1

Taking apart the regex we notice that any word starting with $\texttt{aa}$ or $\texttt{bb}$ is accepted which can be expressed with the following (incomplete) FS: The remaining accepted words must have to end with either $\texttt{aa}$ or $\texttt{bb}$, so you need to "store" a read $\texttt{a}$ (or $\texttt{b}$) and distinguish between the next symbol if ...

1

The DFA starts by reading the first two characters. If they happen to be the same, then it goes to an accepting state and just stays there. Otherwise, it keeps track of the last two characters of the word being read, being in an accepting state whenever they are the same. Instead of writing a state diagram, here are the Myhill–Nerode equivalence ...

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