ISI2016-PCB-CS-6

Question

1. Let L be a regular language over $\{0,1\}$. Define the reverse of the language $L$ to be the language $L^R = \{ w \in \{0,1\}^* \: \: : \: \: \text{ reverse }(w) \in L\}$, where $\text{reverse}(w)$ denotes the string $w$ in reverse. For example $\text{reverse}(0001)=1000$. Show that $L^R$ is regular.
2. Let $L=\{x \: \: : \: \: x \in \{0,1\}^*$, $x$ contains an odd number of $1's$ and $00$ as a substring$\}.$  Construct a regular expression for the language $L$.

Answer 1

Part $(ii)$

Regular Exp where 00 substring is reached when even $\#1s$ = $((0^*10^*1)^*0^*) 00 (0^* 1 0^* (0^*10^*10^*)^*)$

Regular Exp where 00 substring is reached when odd $\#1s$ = $ (0^* 1 0^* (0^*10^*10^*)^*) 00 (0^* 1 0^* (0^*10^*10^*)^*) $

So resulting Regular Expression with 00 as substring and odd $\# 1s$ =  

 

$$\underbrace{((0^*10^*1)^*0^*)}_{Even \quad1s}00\underbrace{(0^* 1 0^* (0^*10^*10^*)^*)}_{Odd \quad1s} + \underbrace{(0^* 1 0^* (0^*10^*10^*)^*)}_{Odd \quad1s}00\underbrace{((0^* 1 0^* (0^*10^*10^*)^*))}_{Even \quad1s}$$

Answer 2

Part $(i)$:
Source: Introduction to Automata Theory, Languages, and Computation, Hopcroft, Ullman