UGC NET CSE | June 2016 | Part 2 | Question: 31

Question

The number of strings of length 4 that are generated by the regular expression $$(0 \mid \epsilon ) 1^+ 2^{*}(3 \mid \epsilon)$$, where $\mid$ is an alternation character, $\{+, *\}$ are quantification characters, and $\epsilon$ is the null string, is:

• A. 08
• B. 10
• C. 11
• D. 12

Answer 1

Given Regex = $(0 \mid \in ) 1^+ 2^{*}(3 \mid \in)$

Assume the regex in 4 parts : W = $(0 \mid \in )$ , X = $1^+$ , Y = $2^*$ , Z = $(3 \mid \in)$

So that regex becomes : WXYZ

X part is compulsory (we must include at least one character from X ). But we have a choice on inclusion of W,Y,Z parts. i.e. we may skip thses parts by selecting NULL or include chracters from these parts as long as our 4 length criteria is satisfied.

We have 8 combinations of (W,Y,Z) i.e. 000,001,010,011 ..etc up to 111.

[ we can not toggle X part ]

Here 1 means inclusion of characters a part and 0 (zero) means skipping a part by selecting NULL. (1 = pick ; 0 = skip)

Considering each combinations of W,Y,Z at a time :

---

1. 000 =>  possible 4 length strings : 1111

explanation for this combination : 000 : means select NULL from each parts i.e. W,Y,Z. So, if we need 4 length strings we must make it up using only X part ( $1^+$). In this particular case only one string 1111

2. 001 => possible 4 length strings : 1113

3. 010 => possible 4 length strings : 1222,1122,1112

4. 011 => possible 4 length strings : 1223,1123

5. 100 => possible 4 length strings : 0111

6. 101 => possible 4 length strings : 0113

7. 110 => possible 4 length strings : 0122,0112

8. 111 => possible 4 length strings : 0123

No common string in the above listing. [ because combinations are exclusive ]
Total 4 length strings = 12

Answer 2

starting with 0 and ending with 3 = 0123,0113,

starting with 0  = 0122,0112,0111

ending with 3 =  1223,1123,1113

without 0 and 3 = 1222,1122,1112,1111

total 12.