809 views
1 votes
1 votes

Write regular expressions for the following languages on {$0, 1$}.
(a) all strings ending in $01$,
(b) all strings not ending in $01$,
(c) all strings containing an even number of $0$’s,
(d) Peter Linz Edition 4 Exercise 3.1 Question 17.d (Page No. 76)
(e) all strings with at most two occurrences of the substring $00$,
(f) all strings not containing the substring $101$.

1 Answer

1 votes
1 votes

(A) : $(0+1)^* 01$

(B) : ∈ + $0$ +$1$ + $(0+1)^* (00+10+11)$

(C) : $(1^*01^*0)^* 1^*$

(E) : I’m not sure about my answer here so I'm Happy to be corrected

        Here we can divide this question into 3 parts :

        $Part$ $1$ : $All$ $the$ $strings$ $having$ $0$ $occurrence$ $of$ $the$ $substring$ $’00’$ 

        $Part$ $2$ : $All$ $the$ $strings$ $having$ $1$ $occurrence$ $of$ $the$ $substring$ $’00’$

        $Part$ $3$ : $All$ $the$ $strings$ $having$ $2$ $occurrences$ $of$ $the$ $substring$ $’00’$ . $Here$ , $we$ $can$                                                        $divide$ $this$ $part$ $into$ $2$ $parts$ :

                 $3A$ : $Strings$ $that$ $contain$ $one$ $occurrence$ $of$ $’000’$ $as$ $substring$.($Since$ $000$ $will$                                                      $have$ $2$ $occurrences$ $of$ $’00’$)

                 $3B$ : $Strings$ $that$ $contains$ $2$ $occurrences$ $of$ $the$ $substring$ $00$ ($No$  $000$ $as$ $substring$)

 

$RegEx$ $for$ $Part$ $1$ : $1^* (01^+)^* (∈ + 0)$

$RegEx$ $for$ $Part$ $2$ : $1^*(01^+)^* 00 (1^+0)^* 1^* $ 

Look at this to know How I obtained this: https://gateoverflow.in/308132/peter-linz-edition-4-exercise-3-1-question-15-page-no-76?show=399638#a399638 

$RegEx$ $for$ $Part$ $3A$ : $1^* (01^+)^* 000 (1^+ 0)^* 1^*$

$RegEx$ $for$ $Part$ $3B$ : $1^* (01^+)^* 00 (1^+0)^* 1^+ 00 (1^+0)^* 1^*$

$Your$ $Regular$ $Expression$ : $Part$ $1$ $+$ $Part$ $2$ $+$ $Part$ $3A$ $+$ $Part$ $3B$

 

(F) : You can do this question by first making a DFA for all the strings having $101$ as substring.

        Now you can convert the Final states into Non Final States and the Non Final states into the Final states ,after this use state removal method to get Regex.

 

 

                           

Related questions

4 votes
4 votes
1 answer
1
1 votes
1 votes
1 answer
2
Naveen Kumar 3 asked Mar 31, 2019
1,792 views
Find regular expressions for the following languages on {$a, b$}.(a) $L =$ {$w : |w|$ mod $3 = 0$}.(b) $L =$ {$w : n_a (w)$ mod $3 = 0$}.(c) $L =$ {$w : n_a (w)$ mod $5 ...
1 votes
1 votes
1 answer
4