Let L be a language whose FA consist of 5 acceptance states and 11 non...
If L leads to FA1, then for Lc, the FA can be obtained by exchanging the final and non-final states.
View all questions of this test
Let L be a language whose FA consist of 5 acceptance states and 11 non...
Solution:
To find the number of acceptance states in Lc, we need to first find the number of non-acceptance states in Lc.
The complement of L, denoted by Lc, consists of all strings that are not in L.
Let's assume that the total number of states in the FA for L is N. Then we can write:
N = number of acceptance states + number of non-acceptance states + 1 (for the dumping state)
We are given that:
number of acceptance states = 5
number of non-acceptance states = 11
1 state is for dumping state
So, N = 5 + 11 + 1 = 17
Now, let's find the number of non-acceptance states in Lc. This will be the same as the number of acceptance states in L.
number of non-acceptance states in Lc = number of strings not in L
Since Lc consists of all strings that are not in L, it will consist of all possible strings over the same alphabet that are not in L.
The total number of strings over an alphabet with n symbols is 2^n. In this case, we are not given the size of the alphabet, but we can assume that it is finite.
So, the number of strings not in L is:
total number of strings - number of strings in L
= 2^n - |L|
= 2^n - 2^5 (since there are 5 acceptance states in L)
= 2^n - 32
Therefore, the number of non-acceptance states in Lc is:
Nc = number of non-acceptance states + number of acceptance states + 1 (for the dumping state)
= 11 + (2^n - 32) + 1
= 2^n - 20
Finally, the number of acceptance states in Lc is:
number of acceptance states in Lc = number of non-acceptance states in L
= 2^n - 20 - 1
= 2^n - 21
Since we don't have any information about the size of the alphabet or the number of states in L, we cannot find the exact value of n. However, we can see that the only option that matches the answer 2^n - 21 for some n is option A (16 acceptance states), since 2^5 = 32 and 2^6 = 64, so n could be 6.
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).