This is the theory of computation. Please explain answer clearly, if you write,

Question

This is the theory of computation. Please explain answer clearly, if you write, please write clearly.

Explanation / Answer

b->the language is not regular, but it does have a (probably nondeterministic) PDA. In this case it is much easier to derive a CFG, which is the following s-> aTbb T-> aTb T-> aTbb T-> ab For the PDA the following strategy should work: For each a that you read push two a's in the stack. When you reach the first b pop two a's. For each following b nondeterministically pop either one a or two a's. If in the last b you manage to pop exactly one a you have an valid string. At the same time you also have to check that your input is a series of a's only, followed by a series of b's only, but that is very easy to integrate with the previous paragraph. I cannot see how you can produce a deterministic PDA to do the job, but that is not necessarily the case. I have not proved it, but I suspect no such DPDA exists, since m does not deterministically depend on n, so using the above to produce a NPDA is probably your best bet.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.