Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Questions  >  Let L be a language whose FA consist of 5 acc... Start Learning for Free
Let L be a language whose FA consist of 5 acceptance states and 11 non final states. It further consists of a dumping state. Predict the number of acceptance states in Lc.
  • a)
    16
  • b)
    11
  • c)
    5
  • d)
    6
Correct answer is option 'A'. Can you explain this answer?
Verified Answer
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
Most Upvoted Answer
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.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Let L be a language whose FA consist of 5 acceptance states and 11 non final states. It further consists of a dumping state. Predict the number of acceptance states in Lc.a)16b)11c)5d)6Correct answer is option 'A'. Can you explain this answer?
Question Description
Let L be a language whose FA consist of 5 acceptance states and 11 non final states. It further consists of a dumping state. Predict the number of acceptance states in Lc.a)16b)11c)5d)6Correct answer is option 'A'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Let L be a language whose FA consist of 5 acceptance states and 11 non final states. It further consists of a dumping state. Predict the number of acceptance states in Lc.a)16b)11c)5d)6Correct answer is option 'A'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Let L be a language whose FA consist of 5 acceptance states and 11 non final states. It further consists of a dumping state. Predict the number of acceptance states in Lc.a)16b)11c)5d)6Correct answer is option 'A'. Can you explain this answer?.
Solutions for Let L be a language whose FA consist of 5 acceptance states and 11 non final states. It further consists of a dumping state. Predict the number of acceptance states in Lc.a)16b)11c)5d)6Correct answer is option 'A'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE). Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of Let L be a language whose FA consist of 5 acceptance states and 11 non final states. It further consists of a dumping state. Predict the number of acceptance states in Lc.a)16b)11c)5d)6Correct answer is option 'A'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of Let L be a language whose FA consist of 5 acceptance states and 11 non final states. It further consists of a dumping state. Predict the number of acceptance states in Lc.a)16b)11c)5d)6Correct answer is option 'A'. Can you explain this answer?, a detailed solution for Let L be a language whose FA consist of 5 acceptance states and 11 non final states. It further consists of a dumping state. Predict the number of acceptance states in Lc.a)16b)11c)5d)6Correct answer is option 'A'. Can you explain this answer? has been provided alongside types of Let L be a language whose FA consist of 5 acceptance states and 11 non final states. It further consists of a dumping state. Predict the number of acceptance states in Lc.a)16b)11c)5d)6Correct answer is option 'A'. Can you explain this answer? theory, EduRev gives you an ample number of questions to practice Let L be a language whose FA consist of 5 acceptance states and 11 non final states. It further consists of a dumping state. Predict the number of acceptance states in Lc.a)16b)11c)5d)6Correct answer is option 'A'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Explore Courses
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev