7
The same "argument" would show that $\mathbb{N}$ is finite since it's the union of finite sets $$\mathbb{N}=\{0\}\cup\{0,1\}\cup\{0,1,2\}\cup ...$$ The point is that knowing that a given property is preserved under a given operation does not mean that it's preserved under "infinite iterations" of that operation.
4
What you draw is an NFA, because you do not have both transition for $a$ and $b$ in two accept states.
Indeed, you need 4 states at least. Because you have 4 different states:
Initial state
Detect $a^*$ strings
Detect $b^*$ string
None of them
You can't merge the first 3 steps because they are exclusive. Now, you can suppose that we can merge the 4th state ...
4
'$R$'
is not used in the literature to indicate languages ... generally we use $L$.
Anyway, the "$\circ$" operator indicates the concatenation of two or more languages. Keep in mind that the concatenation of regular languages is also regular: you can proove this by 'linking' the NFA's/DFA's thath recognize them.
In this case you are concatenating a ...
4
Notice the abuse of notation used. The quote overload symbol $f$ with three meanings which I will now denote differently with $f,f',f''$.
First is map from alphabet to words $$f: \Sigma \rightarrow \Gamma^*$$.
The second is the map between words $$f':\Sigma^* \rightarrow \Gamma^*$$.
The third is the map between languages $$f'':\mathbb{P}(\Sigma^*) \...
3
Just pump up $(M+1)$ $y$'s. Now you get $xy^{M+1}z=a^{(M+1)j+M-j}=a^{M(j+1)}$. Since $M$ is a product of two primes, $M(j+1)$ is a product of at least 3 primes, so $a^{M(j+1)}\notin L_1$, which proves $L_1$ is not regular by the pumping lemma.
3
I'm not sure what $L1, \dots, Lk$ are since you did not define them. The easiest way is probably that of starting with a DFA for $L$ and constructing a NFA for $drop(L)$ (hint in the spoiler below).
Then it should be easy to show that:
If $w \in drop(L)$ then the NFA accepts $w$: use the definition of the function $drop$ to conclude that there must be a ...
3
The words $0^n1$ are pairwise distinguishable, since $0^n10^n$ is a palindrome but $0^n10^m$ isn't (for $n \neq m$).
With a bit more work, you can show that in fact all words are pairwise distinguishable. See for example here or here.
3
You can verify that $010$ is in $(0+1)^*$ but not in $(0^* + 1^*)$. Therefore, $(0 + 1)^* \neq (0^* + 1^*)$.
2
The subset of all palindromes in L is obviously not usually regular, take the simple example $a^*ba^*$ where the subset of palindromes $a^nba^n$ is not regular.
Assume you have an FSM for L (that is an FSM describing and defining L). You can take that FSM and use a simple algorithm to determine if w is in M:
Given a state S, define succ(S, a) as the state ...
2
The unique prefix of the empty word $e$ is $e$, and it does not start with $b$. Therefore $e$ satisfies the condition "no prefix of $e$ starts with $b$" and hence $e$ belongs to $L$.
2
If I understand the question, your problem is the following:
Given a regular language $L$ over alphabet $\Sigma$ and a positive integer $n$, compute the probability that a word chosen uniformly at random from $\Sigma^n$ will be in $L$.
That's equivalent to computing $|L \cap \Sigma^n|$, i.e., the cardinality of the language $L \cap \Sigma^n$. Note that $...
2
You seem to be misunderstanding the statement of the exercise. It wants you to show that if $L$ is a language accepted by a DFA containing two states, then either $L$ is empty, or $L$ contains the empty word, or $L$ contains a word of length 1. Which of the cases holds depends on $L$. More explicitly:
If no state of the DFA is accepting, then $L = \emptyset$...
2
Any regular language upholds the pumping lemma. Hence, if a language doesn't uphold the pumping lemma, it is not a regular language. This is in fact the standard way of proving a language is not regular.
Let us choose $p$ to be the pumping length. Let's now take $0^n=1^n \oplus 1^n$, which is in $A$. This string can be decomposed into three concatenated ...
2
You need to keep doing it an infinite number of times before you reach any infinite languages. So your proof will involve transfinite induction. As Wikipedia says:
Transfinite induction is an extension of mathematical induction to
well-ordered sets, for example to sets of ordinal numbers or cardinal
numbers.
Let P(α) be a property defined for all ...
2
You proved that any finite languages are regular. All the languages that you generated are finite.
2
Here is yet another proof. It is known that the number of integers at most $n$ which are the product of two primes is $o(n)$, see for example this answer, which gives the asymptotic $\frac{n\log\log n}{\log n}$. This means that your language is infinite yet has vanishing asymptotic density. This is impossible for a regular unary language.
1
Take a DFA $D_A$ for $A$ and a DFA $D_B$ for $B$.
Define a DFA $D$ for $A \setminus B$ as follows:
The set of states of $D$ is the cartesian product of the set of states of $D_A$ with the set of states of $D_B$.
The initial state of $D$ is $(a_0, b_0)$ where $a_0$ is the initial state of $D_A$ and $b_0$ is the initial state of $D_B$.
A state $(a,b)$ of $D$ ...
1
For an alphabet of $\{a, b, c\}$ constructing a DFA that accepts all strings not containing the substring 'aa' tells you several things about the number of states you need. Firstly, and this is true for any DFA, you need at least one accepting state. Since your DFA is meant to filter out some strings, it requires a 'trap' or 'dead' state, a state that may ...
1
There is an alternative to the “pumping” lemma which I find easier: After each possible input, determine the set of continuations that would complete a string of the language. You can use each of those sets as a state in the finite state machine for the language, so if there is a finite number of those sets then the language is regular- if there are ...
1
False. There are infinitely many finite language. Just think of {0,1}*. This is a infinite set of finitely long strings. or say, it is union of infinite number of finite languages over {0,1} which have strings of finite length.
False. Union of two non regular languages MAY BE regular but it not the case always. This answer explains it well.
False. Lets have ...
1
Here is one result in the direction you're looking into:
Suppose that $A,B,C$ are languages such that $A$ is a non-regular subset of the regular language $C$, and $B$ is disjoint from $C$. Then $A \cup B$ is non-regular.
For the proof, consider the intersection of $A \cup B$ and $C$. Details left to the reader.
The question you link to concerns the ...
1
Let $S$ be the list of all prefixes of words in $L$. Create a DFA with a state $q_s$ for each $s \in S$, and an additional sink state $q_\bot$. The starting state is $q_\epsilon$, and a state is accepting if it corresponds to a word in $L$. When at a non-sink state $q_s$, upon reading $\sigma$, move to $q_{s\sigma}$ if $s\sigma \in S$, and to $q_\bot$ ...
1
The idea is to prove separately the two inclusions, each of them using induction.
Part 1: $(L_A^*L_B)^+ \subseteq (L_A \cup L_B)^* L_B$
We will prove by induction that for all $n \geq 1$, $(L_A^*L_B)^n \subseteq (L_A \cup L_B)^* L_B$.
When $n = 1$, we need to show that $L_A^* L_B \subseteq (L_A \cup L_B)^* L_B$. This is clear since $L_A \subseteq L_A \cup ...
1
Although I can't do the proof completely right now, maybe looking at $(L_A^* L_B)^+ \subseteq (L_A \cup L_B)^*L_B$ and $(L_A \cup L_B)^*L_B \subseteq (L_A^* L_B)^+$ helps here. So from left to right: If you take a word $w \in (L_A^* L_B)^+$, can you split it up into $0..m$ subwords of the form $(L_A \cup L_B)$ and one postfix-subword of form $L_B$? I hope ...
Only top voted, non community-wiki answers of a minimum length are eligible
