New answers tagged regular-languages
0
If you are working on assignment 2 as I am, my advice is take a good look at lecture slides "Regular Languages" page 7.
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 ...
3
'$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 ...
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.
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.
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 ...
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 ...
3
You can verify that $010$ is in $(0+1)^*$ but not in $(0^* + 1^*)$. Therefore, $(0 + 1)^* \neq (0^* + 1^*)$.
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 ...
2
You proved that any finite languages are regular. All the languages that you generated are finite.
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.
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 ...
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 ...
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 ...
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 ...
0
I believe I can prove that:
a RE using only possessive operators is equivalent to a RE without possessive operators.
any RE can be rewritten to an equivalent RE that uses only possessive operators.
For two expressions $A$ and $B$ to be equivalent means that they define the same language:
$$A\equiv B \implies L(A) = L(B)$$
Let's mark with "$\hat{\ }$" the ...
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$...
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 ...
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$.
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.
0
For this and similar problems you need to first prove a property of finite state machines: The set of lengths of strings that transition from one state to another is either a finite set of integers, or there is a k >= 1, and two finite sets X and Y such that every possible length is either in X, or is equal to n*k + y, where n >= 0 and y is an element of Y.
...
0
Yes, it is regular. It is complicated.
Create an FSA for L.
For each pair of states (Si, Sj) find the set of possible counts of symbols that could lead from Si to Sj. This set can be described in a finite way, it has the form of some constants ci, plus if there is a cycle involved, n*k + di for some fixed k and some constants di, and all n ≥ 0. Example: ...
1
Your initial automaton has two final states. Its reverse should have two initial states. You wanted to avoid that, and added a new initial state.
The proper construction just uses the two initial states. The determinization algorithm can handle that.
1
$L_1$, $L_2$ and $L_4$ are correct (notice that you are not showing that $L_2$ is not regular and $L_4$ is not context-free, which can be done using the appropriate version of the pumping lemma).
As far as $L_3$ is concerned, let $x$ be the number that is encoded in binary and call $x_i$ its $i$-th least significant bit, indexed from $0$. Then, counting ...
Top 50 recent answers are included
