The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

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 as in w is not larger than the number of bs 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 ...
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 ...