How to construct an nfa, Give a construction that assumes

How to construct an nfa

Assignment Help Theory of Computation

Reference no: EM1353188

Suppose that we take strings over the alphabet ∑ = {0,1}. Suppose w is a word, we defi ne sort(w) to be the word obtained by putting all the 0s before the 1s. Thus sort(010) = 001. Let L be any language. We de fine sort(L) = {sort(w)| w ∈ L}.

If L is regular does sort(L) have to be regular? Prove your answer. If your answer is "no" you have to give an explicit example of an L that is regular and a proof that sort(L) is not regular for your particular choice of L. If your answer is "yes" you have to give a construction that assumes you are given a DFA for L and show how to construct an NFA (with or without ε-moves) to recognize sort(L). Obviously a "yes" answer cannot be justi ed by an example. You must give a construction that works for any L.

Reference no: EM1353188

Questions Cloud

What could be the impact on your rm : M is the average income in the United States. What could be the impact on your rm.

Culture and business strategies : Do you feel that one's culture follows a business strategy or vice versa and Why would a company's strategy follow the culture that they are being hosted in?

What is the minimum coefficient of friction that prevent : Two people, one of mass 75kg and the other of mass 60kg, sit in a rowboat of mass 80 kg. With the boat initially at rest, two people, who have been sitting at opposite ends of the boat 3.2 m apart from each other, now exchange seats. How far and i..

Determine the price of the companys stock : Corporation just completed a 3 for 1 stock split. Prior to the split, the stock price was $120 per share. The total market value increased by 5 percent as a result of the split.

How to construct an nfa : Give a construction that assumes you are given a DFA for L and show how to construct an NFA (with or without ε-moves) to recognize sort(L).

Explain what are the positive and negative tradeoffs : Explain what are the positive and negative tradeoffs associated with outsourcing production functions to supplier organization?

Understanding the theory of personality : How would you explain apparent personality differences based on culture, gender, and age? Explain how each theorist would answer this question based on your understanding of his theory of personality.

Communication ethics in corporate culture : Communication Ethics in Corporate Culture and critically evaluate the code of ethics practiced in the corporate world.

Find the value of tax shield : Your company has debt worth $200,000, with a yield of 9%, and equity worth $300,000. It is growing at a 5% rate, and its tax rate is 40%. A similar firm with no debt has a cost of equity of 12 percent.

User Account

All Pages