Third model of computation, Theory of Computation

Assignment Help:

Computer has a single LIFO stack containing ?xed precision unsigned integers (so each integer is subject to over?ow problems) but which has unbounded depth (so the stack itself never over?ows).

In your program you should limit yourself to accessing this with methods like push(i), top(), pop(), and a predicate like empty?(). These will push a value into the stack, return the value stored in the top of the stack (the most recent value pushed), discard the top of stack,
and test the stack for empty, respectively. Don't forget that you have no storage outside of the stack, so you need to work directly with the values in the stack-you can't pull a value out of the stack and assign it to some other variable. Similarly, while you can call input() as
often as you wish, the only way to store the value of the input is to push it directly into the stack (e.g., push(input())).

(a) Sketch an algorithm to recognize the language of strings of the form wcwr where w is any sequence of ‘a's and ‘b's and wr is exactly the same sequence of ‘a's and ‘b's in reverse order, so these are all palindromes over the alphabet {a, b, c} in which 'c' occurs only as the middle symbol. It includes strings like:

abbbcabbb aca ababacababa c

(In the last example there are no ‘a's or ‘b's, the "re?ected" string is empty.)

(b) What is your intuition about recognizing this language within the second model (i.e., using just a single counter)?

(c) What is your intuition about the possibility of recognizing the language of strings of the form wcw, where w is an arbitrary string of ‘a's and ‘b's? This is the set of strings made up of any sequence of ‘a's and ‘b's followed by a 'c' and then exactly the same sequence of ‘a's and ‘b's in exactly the same order; it's referred to as the (deterministic) copy language.


Related Discussions:- Third model of computation

Strictly local languages, While the SL 2 languages include some surprising...

While the SL 2 languages include some surprisingly complex languages, the strictly 2-local automata are, nevertheless, quite limited. In a strong sense, they are almost memoryless

Closure properties to prove regularity, The fact that regular languages are...

The fact that regular languages are closed under Boolean operations simpli?es the process of establishing regularity of languages; in essence we can augment the regular operations

Automata, As we are primarily concerned with questions of what is and what ...

As we are primarily concerned with questions of what is and what is not computable relative to some particular model of computation, we will usually base our explorations of langua

Language accepted by a nfa, The language accepted by a NFA A = (Q,Σ, δ, q 0...

The language accepted by a NFA A = (Q,Σ, δ, q 0 , F) is NFAs correspond to a kind of parallelism in the automata. We can think of the same basic model of automaton: an inpu

Give a strictly 2-local automaton, Let L 3 = {a i bc j | i, j ≥ 0}. Give ...

Let L 3 = {a i bc j | i, j ≥ 0}. Give a strictly 2-local automaton that recognizes L 3 . Use the construction of the proof to extend the automaton to one that recognizes L 3 . Gi

Flow charts, https://www.google.com/search?q=The+fomula+n%3D%28x%3D0%29%2F%...

https://www.google.com/search?q=The+fomula+n%3D%28x%3D0%29%2F%281%3D2%29.The+value+x%3D0+and+is+used+to+stop+the+algerithin.The+calculation+is+reapeated+using+values+of+x%3D0+is+in

Discrete math, Find the Regular Grammar for the following Regular Expressio...

Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd