# Tag Info

2

The two are not actually same kind of items. $\epsilon$ is a word while $\emptyset$ is a set of words (a.k.a. a language). $\{\epsilon\}$ is the language containing only the empty word (i.e. $|\{\epsilon\}|=1$ and it is different from $\emptyset$ which doesn't contain any word ($|\emptyset|=0$). For a language $L$, $L^*$ stands for the concatenation of 0 ...

2

Suppose that $w\in L_{DFA_{MIN}}$, say $w=a_1\ldots a_n$, where each $a_k\in\Sigma$. Then there is a sequence $\langle T_0,\ldots,T_n\rangle$ of states in $Q_{MIN}$ such that $T_0=q_{s_{MIN}}$, $T_n\in F_{MIN}$, and $\delta_{MIN}(T_k,a_{k+1}=T_{k+1})$ for $k=0,\ldots,n-1$. Since $T_n\in F_{MIN}$, there is a $q_n\in T_n\cap F$. Suppose that $q\in T_n$; $q$ ...

1

The set of strings in the English language is presumably finite. Why don't you create a DFA to recognize all of them and then negate the acceptance? Alternatively, create the regex of all English words: (Aardvard | .... | zymurgy) and take its complement.

1

A word $w_1w_2\dots w_n$ will be accepted by $L_1$ if all the words $w_1w_2\dots w_m$, for $m\leq n$ are accepted by $L$. So you can start from a finite automaton that defines $L$ and you modify it so that it rejects the word that is feeded to it as soon as any of its intermediate states rejects. You can do this by collecting all the states that are ...

1

You’re having trouble because $L$ is regular. If by $\Bbb N$ you mean the set of non-negative integers, then $L=\Sigma^*$, because any word $w\in\Sigma^*$ can be written in the form $a^0wb^0$, where $|w|\ge 0$. If by $\Bbb N$ you mean $\Bbb Z^+$, the set of positive integers, then $$L=\left\{awb\in\Sigma^*:|w|\ge 1\right\}\;,$$ which corresponds to the ...

Only top voted, non community-wiki answers of a minimum length are eligible