in Theory of Computation retagged by
251 views
2 votes
2 votes

please explain it how to solve such question in exam

Ans: 22

in Theory of Computation retagged by
251 views

3 Answers

3 votes
3 votes
Length $1$ strings are :- $“a”$

Length $2$ strings are:-$”aa”,”ab”,”ac”$

Length $3$ strings are :-$ “aaa”,”abc”,”abb”,”acc”,”aac”,”aab”$

Length $4$ strings are :- $“aaaa”,”aabc”,”abca”,”abcb”,”abcc”,”aabb”,”aacc”,”abbb”,”accc”,”aaab”,”aaac”,”abbc”$

So total no of string of less than or equal to 4 is =$1+3+6+12=22$.
2 votes
2 votes
Given R = $a.(a+bc)^*.b^*.c^*$

Strings of length 4 = $a _ _ _ $

Case 1 : $1$ $bc$ selected from $(a+bc)^*$

Now you have $1$ blank and you can choose $1$ character from $a, b, c$.

$\text{number of strings} = 3$.

Case 2 : $0$ $bc$ selected from $(a+bc)^*$

Now you have $3$ blanks and you can choose $3$ characters from $a, b, c$.

$\text{number of strings} = {5 \choose 3} = 10$.

Strings of length $3$ = $a _ _ $

Case 1 : $1$ $bc$ selected from $(a+bc)^*$

Now you have no blanks.

$\text{number of strings} = 1$.

Case 2 : $0$ $bc$ selected from $(a+bc)^*$

Now you have $2$ blanks and you can choose $2$ characters from $a, b, c$.

$\text{number of strings} = {4 \choose 2} = 6$.

Strings of length $2$ = $a _ $

Now you have $1$ blanks and you can choose $1$ character from $a, b, c$.

$\text{number of strings} = 3$.

There is only one string of length $1$ possible.

$1$ string of length $4$ is counted twice $abcc$ and $1$ string of length $3$ is counted twice $abc$.

$\text{Total strings} = 3 + 10 + 1 + 6 + 3 + 1 - 2 = 22$.
1 vote
1 vote
Given $R = a.(a+bc)^*.b^*.c^*$

Case 1 : $1$ $bc$ is selected from $(a+bc)^*$.

One blank space is left and we can choose $1$ character from $a, b, c, \epsilon$.

$\text{Number of strings} = 4$.

Case 2 : $0$ $bc$ is selected from $(a+bc)^*$.

Now 3 blank spaces is left and we can choose $3$ characters from $a, b, c, \epsilon$.

$\text{Number of strings} = {6 \choose 3} = 20$.

Now we have counted $2$ strings twice - $abc$ and $abcc$.

$\text{Total strings} = 20 + 4 - 2 = 22$.

2 Comments

why 6C3? i didnt understand?
0
0
So, we have our string in the form $a _ _ _ $.

Case 2 : And we can fill these 3 blanks with characters from $a, b, c, \epsilon$.

Means number of $a$'s plus number of $b$'s plus number of $c$'s plus number of $\epsilon$'s equals 3.

Every non-negative integral solution of the above equation will correspond to a unique string.

Few examples -

$a = 0, b = 0, c = 0, \epsilon = 3 \implies a$.

$a = 3, b = 0, c = 0, \epsilon = 0 \implies aaaa$.

$a = 1, b = 1, c = 1, \epsilon = 0 \implies aabc$.

$a = 0, b = 1, c = 1, \epsilon = 1 \implies abc$.

Now, the number of non-negative integral solutions of the equation $a + b + c + \epsilon = 3$ are ${3+4-1 \choose 4-1}$ = 20.
2
2