1

Here are the first few even natural numbers: $$ \begin{array}{r} 0 \\ 10 \\ 100 \\ 110 \\ 1000 \end{array} $$ Here are the first few odd natural numbers: $$ \begin{array}{r} 1 \\ 11 \\ 101 \\ 111 \\ 1001 \end{array} $$ Notice any pattern? You take it from here.


1

This proof looks correct. You can shorten it a bit (it doesn't need to be so descriptive), and you would get the following proof: $h(L)=h(L(r_1\cup r_2))=h(L(r_1)\cup L(r_2)) = h(L(r_1))\cup h(L(r_2)) = L(r'_1)\cup L(r'_2)=L(r'_1\cup r'_2)$ Where the transition $h(L(r_1)\cup L(r_2)) = h(L(r_1)) \cup h(L(r_2))$ can be shown for any function $h$ (not ...


1

The $+$ sign stands for union, but you got the order of operations wrong. Your regular expression is the sum of $(b+c)^*$ and $$ (b+c)^*((a+aa)(b+c)^+)^*(a+aa)(b+c)^*. $$


1

Note that $abbbb+aba^*bbb = aba^*bbb$. Also, note that you can "factorize" common expressions in the parentheses. Your regular expression is equivalent to $b(a(\varepsilon + ba^*b)bb)^*$ (I don't know if it can be simplified again).


1

They're not regular, but finite state transducers can be used to generate and recognize complicated morphology, such as Finnish numerals. – phipsgabler May 7 '20 at 7:31 Similarly, a long time ago I worked using FST to identify multiword verbal expressions (such as 'tomar el pelo' [to pull somebody's leg]) in Spanish texts; words were previously tagged. ...


1

Any of the following should work: $(1+01)^*(0+\epsilon)$ $(0+\epsilon)(1+10)^*$ $1^*(011^*)^*(0+\epsilon)$ $(0+\epsilon)(11^*0)^*1^*$


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