How many states would the dfa have

Assignment Help Theory of Computation

Reference no: EM132104992

Problem : Smaller NFA

In this problem we'll see a very clear example of how NFAs can be built to recognize a language using much fewer states than a DFA would. Consider the following language L: 'Strings of a's, b's, and c's, that do NOT contain at least one of those 3 letters.'

So for example, accca would be accepted, because it does not contain b, as would bbc which does not contain any a's, and bb winch does not contain any a's or c's, but caba would be rejected because it contains all 3 letters of the alphabet in it.

Build a DFA with at most 8 states that recognizes L.

Build an NFA with at most 4 states that recognizes L.

If instead of 3 letters, your alphabet had k letters, and you build a DFA and an NFA for the language the same way you built them in parts a and b, how many states would the DFA have? How' many states would the NFA have?

Reference no: EM132104992

Questions Cloud

Find out the additional business : Assume there is sufficient capacity for the special order. How do i use differential analysis to find out if the additional business should be accepted or rejec

Give a new yes-instance of problem partition : Can the multi-set S be partitioned into two multi-sets Sa and Sb such that the sum of the integers in Sa is exactly equal to the sum of the integers in Sb.

What amount will accounts receivable be shown : In Razz's budgeted balance sheet at December 31, at what amount will accounts receivable be shown

What are the major challenges fund managers : What are the major challenges fund managers face when they try to raise money?

How many states would the dfa have : If instead of 3 letters, your alphabet had k letters, and you build a DFA and an NFA for the language the same way you built them in parts a and b.

Reporting increase an investment value : Does the use of the accelerated depreciation method (instead of straight line) for income tax reporting increase an investment's value?

Account balances of two accounts : The change in the account balances of these two accounts resulted in total expenses:

Explore the use of a one-time pad version of vigenere cipher : Encrypt the plaintext sendmoremoney with the key stream 2 9 0 1 7 23 15 21 14 11 11 2 8 9 using the ciphertext produced find a key.

What is th capm beta of the portfolio : What is the expected return on a portfolio that has R6000 invested in the risk free security and R4000 invested in the market portfolio?

User Account

All Pages