retagged by
14,052 views
39 votes
39 votes

Which of the following languages is regular?

  1. $\left\{ww^R \mid w \in \{0, 1\}^+\right\}$

  2. $\left\{ww^Rx \mid x,w  \in \{0, 1\}^+\right\}$

  3. $\left\{wxw^R \mid x, w \in \{0, 1\}^+\right\}$

  4. $\left\{xww^R \mid x, w \in \{0, 1\}^+\right\}$

retagged by

2 Answers

Best answer
44 votes
44 votes

Correct Option: C

  1. CFL
  2. CFL
  3. Regular, language is string starting and ending with the same symbol and having length at least $3$. e.g. $0x0$ or $1x1$
  4. CFL

http://gatecse.in/wiki/Identify_the_class_of_the_language

edited by
1 votes
1 votes

The regular expression corresponding to option C is:
0 (0+1)+ 0 + 1 (0+1)+ 1
Any string which begins and ends with same symbol, can be written in form of “wxwR
For example consider a string: 10010111, in this string “w=1” , “x= 001011” and wr = 1. Hence any string which begins and ends with either “0” or with “1” can be written in form of “wxwR” and L={wxwR | x,w ϵ {0,1}+ } is a regular language.

 

Answer:

Related questions

38 votes
38 votes
3 answers
1
Kathleen asked Sep 21, 2014
15,260 views
Which of the following is TRUE?Every subset of a regular set is regularEvery finite subset of a non-regular set is regularThe union of two non-regular sets is not regular...
34 votes
34 votes
5 answers
2
Kathleen asked Sep 21, 2014
21,127 views
How many $3$-to-$8$ line decoders with an enable input are needed to construct a $6$-to-$64$ line decoder without using any other logic gates?$7$$8$$9$$10$
27 votes
27 votes
3 answers
3
go_editor asked Apr 23, 2016
8,413 views
Consider the following Finite State Automaton:The minimum state automaton equivalent to the above FSA has the following number of states:$1$$2$$3$$4$
43 votes
43 votes
6 answers
4
Kathleen asked Sep 21, 2014
13,285 views
Consider the following Finite State Automaton:The language accepted by this automaton is given by the regular expression$b^*ab^*ab^*ab^*$$(a + b)^*$$b^*a(a+b)^*$$b^*ab^*a...