1,526 views
2 votes
2 votes

Is the following two languages regular?

  1. L = { $w$ | the number of occurrences of $'01'$ in $w$ is equal to the number of occurrences of $'10'$}
  2. Late(L) = {$x\in \Sigma^*$ : for some $a\in \Sigma$, string $ax\in L$ where $L$ is regular}

(A) Only $I$        (B) Only $II$        (C) Both $I$ & $II$        (D) Neither $I$ nor $II$

1 Answer

Best answer
4 votes
4 votes

I.  is regular , all strings over {0,1} that start and ends with same symbol.

II. is also regular. we need to remove first symbol from stings accepted by L 

Design DFA for L, Move with one transition from start state, and the states we reach, say some Q,mark them as new start state, it seems we have more than one start states, then add a new state as start state and  connect it with these Q with null move. 

Example

L = { all strings over {0,1} those start with 00 }, having regular expression 00(0+1)* 

DFA for L

on giving symbols { 0,1} at start state we reach to q1 and q3, add new start state and connect it with q1 and q3 with ∊ moves.

After removing Null moves (∊-moves) , we have new DFA for Late(L)

having language Late(L) = { all strings over {0,1} those starts with 0 } having regular expression 0(0+1)*

selected by

Related questions

1 votes
1 votes
1 answer
1
Gate Mm asked Dec 8, 2015
2,596 views
L1 = {ambn | m+n = Even} L2 = {ambn | m-n = 4}(a) L1 is Regular, L2 is Not Regular(b) Both are Regular(c) Both are Non- Regular(d) L2 is Regular, L1 is Not Regular
0 votes
0 votes
1 answer
2
srestha asked May 24, 2018
750 views
Is it regular?$\left \{ \left ( 0^{n} \right )^{m}|n<m,n,m\geq 1 \right \}$
12 votes
12 votes
1 answer
3
Utk asked Dec 30, 2015
2,203 views
Consider following languages :L1 = { wxwy | x,w,y $\in$(a + b)+ } ,L2 = { xwyw | x,w,y $\in$(a + b)+ } ,L3 = { wxyw | x, y, w $\in$(a+b)+ } How can we say that L1 , L2 ar...
1 votes
1 votes
1 answer
4
Isha Karn asked Oct 25, 2014
1,848 views
{ wxw | w belongs to {0,1}* , x belongs to {0,1}+ }