New answers tagged regular-expressions
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^*) \...
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$ ...
3
You haven't defined your language, but presumably
$$
L \cap [^*0+0](+0])^* = \{ [^n[0+0](+0])^n : n \geq 0 \},
$$
where I replaced parentheses with square brackets. The latter language is essentially $\{a^nb^n : n \ge 0 \}$ in disguise, and so isn't regular. It follows that $L$ isn't regular as well.
3
You can verify that $010$ is in $(0+1)^*$ but not in $(0^* + 1^*)$. Therefore, $(0 + 1)^* \neq (0^* + 1^*)$.
0
There is a trivial algorithm to find the minimum regular expression equivalent to a given one:
Go over all regular expressions in nondecreasing order of length. For each one, check whether it is equivalent to the original regular expression. Return the first one which is.
To check equivalence, convert the regular expressions to NFAs, then to DFAs, then ...
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 ...
2
Expanding on Daniel Martin's answer.
None of the following interpretations yields a regular language:
$L = \{ w \in \{a,b\}^* : \exists n \ge 0, \; w = a^n b^n \}$
$L$ contains all the words $w \in \{a,b\}^*$ such that the number of $a$s in $w$ is not larger than the number of $b$s in $w$.
$L$ contains all the words $w \in \{a,b\}^*$ such that the number ...
1
As the comments say, it isn't completely clear what you mean by "matching", but if you mean that for any positive integer $n$, the string $\mathtt{a}^n\mathtt{b}^n$ (that is, the string of $n$ "$\mathtt{a}$"s followed by $n$ "$\mathtt{b}$"s) is in the language, but $\mathtt{a}^n\mathtt{b}^{n-1}$ is not in the language, then what you say is correct: $L$ is ...
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 ...
1
In order to solve this exercise, we need to come up for regular expressions for two classes of words:
Words of the form $x00$, where $x \neq \epsilon$ and the only occurrence of $00$ is at the end.
Words of the form $x01$, where $x \neq \epsilon$ and the only occurrence of $01$ is at the end.
Let us start with the first class. For starters, $x$ must end ...
Top 50 recent answers are included
