Let the following two languages over the alphabet E= {a,b} be given: L = {ababka |...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Let the following two languages over the alphabet E= {a,b} be given: L = {ababka | k No} L2= {abkbka | ke No} Both languages are context free, but only one of them is regular. (a) Which of the two languages is regular? Show the regularity of that language by giving an ap- propriate language generator or language acceptor (for example a DFA, NFA, regular expression or regular grammar). (b) Which of the two languages is not regular? 1) Show that this language is context free by giving an appropriate language generator or language acceptor (for example a context free grammar or a pushdown automaton). 2) Show that the language is not regular. You may use either the Pumping Lemma or the Myhill-Nerode Theorem. Let the following two languages over the alphabet E= {a,b} be given: L = {ababka | k No} L2= {abkbka | ke No} Both languages are context free, but only one of them is regular. (a) Which of the two languages is regular? Show the regularity of that language by giving an ap- propriate language generator or language acceptor (for example a DFA, NFA, regular expression or regular grammar). (b) Which of the two languages is not regular? 1) Show that this language is context free by giving an appropriate language generator or language acceptor (for example a context free grammar or a pushdown automaton). 2) Show that the language is not regular. You may use either the Pumping Lemma or the Myhill-Nerode Theorem.
Expert Answer:
Related Book For
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill
Posted Date:
Students also viewed these programming questions
-
re Regular Languages and Finite Automata (a) Let L be the set of all strings over the alphabet {a, b} that end in a and do not contain the substring bb. Describe a deterministic finite automaton...
-
In a Hopfield neural network configured as an associative memory, with all of its weights trained and fixed, what three possible behaviours may occur over time in configuration space as the net...
-
At one time the Thames River in England supported an abundant community of fish. Pollution then destroyed all the fish in a 40-mile stretch near its mouth for a 45-year period beginning in 1915....
-
Research by R. Pyhala et al. shows that young adults who were born prematurely with very low birth weights (below 1500 grams) have higher blood pressure than those born at term. The study can be...
-
2 . Find the slope of the line represented and y - intercept by the following equation and draw the graph: Y = 3 x - 2
-
A vertical shaft passes through a bearing and is lubricated with an oil having a viscosity of \(0.2 \mathrm{~N} \cdot \mathrm{s} / \mathrm{m}^{2}\) as shown in Fig. P6.85. Assume that the flow...
-
De la Renta Chocolate Company produces chocolate bars. The primary materials used in producing chocolate bars are cocoa, sugar, and milk. The standard costs for a batch of chocolate (4,800 bars) are...
-
what is developmental psychology (or developmental science)? What do developmental psychologists/scientists do? What is the benefit of developmental psychology/science? Why study developmental...
-
A firm needs to fully satisfy the demand, which is fixed to 900 units and generates unit revenue of $10. However, its production is subject to the random yield. That is, only a random percentage of...
-
The point of best quantity and best price (q+,p+) to maximize profit is shown on the graph. Compute the Consumer's surplus (shaded in yellow), for this product at the point (q+,p+). Note: You will...
-
Given a parallel Stream , which method would you use to obtain an equivalent serial Stream ? A. unordered() B. reduce() C. concat() D. stream() E. boxed() F. None of the above
-
What is a possible output of the following application? A. {1975=[Escort], 1967=[ Mustang, Thunderbird]} B. {Escort=[1975], Thunderbird=[1967], Mustang=[1967]} C. The code does not compile. D. The...
-
What is the output of the following application? A. 50 B. 51 C. The code does not compile because of the lambda expression. D. The code does not compile for a different reason. E. The code compiles...
-
Given the following code snippet, what statement about the values printed on lines p1 and p2 is correct? A. They are always the same. B. They are sometimes the same. C. They are never the same. D....
-
Assuming the proper generic types are used, which lambda expression can be assigned to a ToDoubleBiFunction functional interface reference? (Choose three.) A. (Integer a, Double b) -> {int c; return...
-
What is the role of a project manager? What have suggested skills for all project managers and for information technology project managers? Why is leadership so important for project managers? How is...
-
Explain why it is not wise to accept a null hypothesis.
-
John Williams (age 42) is a single taxpayer, and he lives at 1324 Forest Dr., Reno, NV 89501. His Social Security number is 555-94-9358. John's earnings and withholdings as the manager of a local...
-
Steve Jackson (age 51) is a single taxpayer living at 3215 Pacific Dr., Del Mar, CA 92014. His Social Security number is 465-88-9415. In 2012, Steve's earnings and income tax withholding as the...
-
The following additional information is available for the Dr. Ivan and Irene Incisor family. Ivan and Irene have the following investment income, in addition to that reported in Chapter 1: Dividends...
-
Consider a stochastic process such that the underlying security \(S\) follows the model: \[d S_{t}=\mu S_{t} d t+\sigma_{t} S_{t} d Z_{t}\] where \(Z\) is a standard Brownian motion. Suppose the...
-
Calculate the solution to the following SDE: \[d X_{t}=\alpha\left(m-X_{t} ight) d t+\sigma d B_{t}\] with \(X_{0}=x\). The process satisfying this equation is called the meanreverting...
-
If \(X_{t} \sim N\left(0, \sigma^{2} t ight)\) and \(Y_{t}=e^{X_{t}}\), calculate the pdf of \(Y_{t}\). Calculate \(\mathbf{E}\left[Y_{t} ight]\) and \(V\left(Y_{t} ight)\). Calculate the transition...
Study smarter with the SolutionInn App