18
@Vladislav's answer is probably more interesting, but observe that every language over an alphabet $\Sigma$ is a subset of $\Sigma^*$, which is certainly a regular language.
8
No. Let $L$ be the language of balanced bracket sequences, and $L_1$ be the language of arbitrary bracket sequences. Then $L \subset L_1$, $L$ is not regular (you can prove it using pumping lemma), but $L_1$ is clearly regular.
3
The answer depends on whether $L_1$ is a language over $\{a,b\}$ or over $\{a,b,c\}$.
$L_1$ is a language over $\{a,b\}$
In this case, the easiest way to proceed is using closure operations. Show first (by constructing a DFA) that the following language is regular:
$$
L_2 = \{wcv \mid |w|_a+2|v|_b \equiv 3 \bmod 5 , w,v \in \{a,b\}^*\}.
$$
Your language is ...
2
Any regular expression satisfies $r^+ = rr^* = r^*r$. In fact, one often defines $r^+$ using one of these formulas, usually $r^+ := rr^*$.
1
Given a transition function $\delta\colon Q\times\Sigma\to Q$, the standard argument proceeds by defining an extended transition function $\hat{\delta}\colon Q\times\Sigma^*\to Q$ (following the notation in Sipser)
that acts on strings (see J. E. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata Theory, Languages and Computations 3ed., section 2....
1
The first step is to clarify what is being asked: do you mean can every infinite regular language be decomposed in this way, or is it possible that some infinite regular language can be decomposed in this way? Your question does not make this clear.
For the first version of the question, try considering the following language: $b \cup a^*$. Can this be ...
1
For every $i=0,\dots,4$, there exists a regular expression $W_i$ for the language of all words $w$ such that $|w|_a \bmod 5 = i$.
For example:
$$
((b+c)^*a)^i ( ((b+c)^*a)^5)^*(b+c)^*
$$
Similarly, for every $j=0,\dots,4$, there exists a regular expression $Z_j$ for the language of all words $z$ such that $2|z|_b \bmod 5 = j$.
Then a regular expression ...
1
The language of all words not containing $abc$ as a subword can be handled by focussing on the letter $b$.
Whenever it occurs in the string we should check that one of the following conditions hold:
it is the first letter of the string
it is directly after another $b$ or after a $c$,
or symmetrically
it is directly before ...
it is the last letter of the ...
1
Design a DFA that recognizes "abc" (make sure to include all transitions). Complement it (make accepting states non-accepting, and make non-accepting states accepting) in order to get a DFA for $L = \Sigma^* \setminus \{ abc \}$. Finally, write down the regular expression of the complemented DFA.
As a brute force solution that does not use DFAs: write a ...
1
Take $a^nb$ and $a^mb$ for n != m. Since the first can be followed by $a^n$ and the second can’t, they are in different equivalence classes. Therefore the number of equivalence classes is not finite.
C isn’t even needed.
Only top voted, non community-wiki answers of a minimum length are eligible
