Reference no: EM131212476
Theory of Computation Assignment
1. Find regular expressions for the following languages:
a. L = {an bm : n ≥ 3, m is odd}
b. L = {an bm : n + m is odd}
c. L = {w € {a, b}* : |w| mod 3 ≠ 0}
2. Let r1 and r2 denote regular expressions. Which of the following statements are true?
a. (r1*)* ≡ r1*
b. (r1*)( r1 + r2)* ≡ (r1 + r2)*
c. ( r1 + r2)* ≡ (r1* r2*)*
d. (r1 r2)* ≡ (r1* r2*)
3. Find NFA (with λ-transitions) that accepts the language corresponding to the regular expression ab*aa + bba*ab.
4. Find NFA (with λ-transitions) that accepts the language corresponding to the regular expression (a + b)* b (a + bb)*.
5. Recall that a "left-linear grammar" is a grammar in which all non-terminals (i.e. variables) are on the left end of the right side of production rules, while a "right-linear grammar" is a grammar in which all non-terminals (i.e. variables) are on the right end of the right side of production rules.
a. Find a left-linear grammar that generates L = {an bm : n ≥ 3, m ≥ 2}
b. Find a right-linear grammar that generates L = {an bm : n ≥ 3, m ≥ 2}
6. Recall that a "(right) regular grammar" is a right-linear grammar in which production rules belong to these three formats: A → λ (empty string); A → a (terminal alphabet symbol); A → aB (terminal followed by non-terminal). Find a regular grammar that generates all strings over {a, b} * with no more than two a's.
|
Sum up the responsibility of hr management
: The textbook identified several issues that arise in the field of human resource (HR) management. Sum up the responsibility of HR management to address and solve these problems.
|
|
What is the total wtp for 3 tons of cleanup
: If cleaning up 2 tons were to cost $12, is the WTP in this small community sufficient to finance it? What are the two potential reasons a voluntary cleanup might nevertheless fail?
|
|
International strategy at the crossroads
: Case Study - ABLE TRANSLATIONS: INTERNATIONAL STRATEGY AT THE CROSSROADS - The paper is well organized and the flow is easy to follow. Major points have been explained in sufficient depth to be understood. The paper has been checked for spelling an..
|
|
Anticipate in the hospitality industry
: Looking beyond technology, discuss the differences you anticipate in the hospitality industry over the next 20 years. Now look forward to the next 50 years. How will things have changed by then?
|
|
Find nfa that accepts language to regular expression
: Find a left-linear grammar that generates L = {an bm : n ≥ 3, m ≥ 2}. Find NFA (with λ-transitions) that accepts the language corresponding to the regular expression ab*aa + bba*ab.
|
|
Whether the government should use a tariff or a quota
: You are employed in the Ministry of the Economy and have been asked to provide a briefing on whether the government should use a tariff or a quota. - What will you say in your presentation?
|
|
Present one of these papers during class
: Complete two short papers and present one of these papers during class (schedule TBA). Your papers should synthesize an article taken from the business press (see possible choices below) that is related to the paper topic and answer one of the pro..
|
|
Wage gap between men and women runs deep-persists
: Notwithstanding the advancement of women in the professions (law and medicine, in particular), the wage gap between men and women runs deep and persists. Are the societal expectations of earning power between men and women so ingrained that even ..
|
|
Graph the marginal costs and marginal benefits of cleanup
: Fill in the marginal columns, and identify the efficient cleanup level. At the efficient cleanup level, what are the net benefits to the family? What are the net benefits to the family if the floor is completely clean?
|