6
Regular expressions without Kleene star define finite languages. You can prove this by induction on the structure of the regular expression. In contrast, $a^*$ is a regular expression which defines an infinite language.
We could try to define $a^*$ using concatenation and union:
$$ a^* = \epsilon + a + a^2 + a^3 + \cdots $$
Unfortunately, the required ...
5
Hint: prove that $3MAJ(L_1, L_2, L_3) = (L_1 \cup L_2\cap L_3) \ \cap \ (L_2 \cup L_1\cap L_3) \cap \ (L_3 \cup L_1\cap L_2)$.
3
Given a DFA $A$ for $L$, construct an NFA which operates as follows:
The NFA starts by guessing a state $q$ which will be the state that $A$ is on after reading $x$.
The NFA will maintain two states, $q_1,q_2$, the first initialized at the initial state of $A$, the second initialized at $q$.
For each symbol $\sigma$ read, the NFA guesses a new symbol $\tau$ ...
3
Try to express in natural language what $\overline{L}$ contains; that is, what words $L$ doesn't contain. Most obviously, it's "words of the form $0^m0^n$, with $m = n$." However, it also contains "words that are not of the form $0^m1^n$", such as "$101010$". That's why the intersection with $0^*1^*$ is employed, to not bother ...
3
Consider the intersection of your language $L$ with the regular language $L' = \{b^r a^m \mid r,m \ge 0 \}$.
Then $L \cap L'$ contains all the words of the form $a^k b^r a^m$ where $k=0$ and $m=k+r=r$. That is, $L \cap L' = \{ b^r a^r \mid r \ge 0 \}$, which is a well-known non-regular language.
2
The formulation
every substring 000 appears after every 1
is extremely ambiguous. However, given the proposed solution, here is how we are supposed to interpret it. Let $w$ and $x = x_0 \ldots x_{m-1}$ be words. We say that $x$ occurs in $w$ at position $i$ if $$w_i w_{i+1} \ldots w_{i+m-1} = x_0 x_1 \ldots x_{m-1}.$$
The language in question consists of ...
2
In my copy of the book, third edition, this is Theorem 1.25. From its proof, I quote:
The theorem remains true if they have different alphabets, $\Sigma_1$
and $\Sigma_2$. We would then modify the proof to let $\Sigma = \Sigma_1\cup \Sigma_2$.
What is suggested here is that in advance we assume the two alphabets to be equal, i.e., before we start the ...
2
Indeed, $abaaabbb \notin L_1$ because the string is not of the form $(a^nb^n)^m$ which is the repetition of a fixed string with the same number of $a$ and $b$.
The language $L_2$ is the Kleene closure of $\{a^nb^n \mid n\ge1\}$, consisting of all arbitrary concatenations of strings of the form $a^nb^n$. We can choose different strings of this form, and do ...
2
Let $p$ be the pumping length of your language.
As you say, the string $s$ can be written as $s = xyz$ where $|xy| \le p$.
By the choice of $s=0^p 1^p$, you know that the first $p$ characters of $s$ are all $0$, therefore $xy$ (which contains at most $p$ character) must be a string containing only $0$s.
Since $y$ is a suffix of $xy$, $y$ must also contain ...
2
Let's consider 3 regular languages $L_1$, $L_2$ and $L_3$. By Kleene's theorem, there exist 3 DFA $\mathcal{A}_1 = (Q_1, \delta_1, q_1, F_1)$, $\mathcal{A}_2 = (Q_2, \delta_2, q_2, F_2)$ and $\mathcal{A}_3 = (Q_3, \delta_3, q_3, F_3)$ that recognize respectively $L_1$, $L_2$ and $L_3$. Let $\mathcal{A} = (Q, \delta, q_0, F)$ an automaton defined by:
$Q = ...
1
Is there a general way to do it? The answer is yes: one way to do it is to find a DFA that accepts $L$ (for example with the powerset construction), make it complete (by adding a sink state), and swap final states and non-final states. The automaton is deterministic, but it is a special case of non deterministic.
Is there a polynomial time way to do it? I ...
1
This language can be described as 'zero or more zeroes followed by zero ore more ones, where if the number of zeroes is even, so are the number of ones, and vice versa'.
So you just need to keep track of the parity of both the zeroes and ones, and if they match, accept.
1
If we take $L = \{a^n \mid n \in \mathbb{N}\}$, then $L' = \{a^{2n} \mid n \in \mathbb{N}\}$, which is a perfectly fine regular language. Or even more trival, we could observe that $\emptyset' = \emptyset$.
As such, it does not hold that $L'$ is never regular for a regular language $L$. This means that answering the question will involve constructing a ...
1
Any word can be written as a concatenation of runs. For example,
$$ aaabbabaccbbbc = a^3b^2a^1b^1a^1c^2b^3c^1. $$
Each run is a positive power of a symbol, and the constraint is that two adjacent runs are powers of different symbols. Each word can be decomposed into runs in a unique way.
The regular expression $(a+b)^*c^*(a+b)^*$ captures all words with at ...
1
Here is a way to describe a binary string in which every 00 must have at least two 1s before it.
It is a string that
$\quad$ starts with zero or one 0;
$\quad$ followed by zero or more blocks, where each block is
$\quad\quad$ either one or more 1s followed by a 0, such as 10, 110, 1110, etc,
$\quad\quad$ or two or more 1s followed by two 0s, such as 1100, ...
Only top voted, non community-wiki answers of a minimum length are eligible
