User Account

All Pages

Push down automata, Theory of Computation

Assignment Help:
Construct a PDA that accepts { x#y | x, y in {a, b}* such that x ? y and xi = yi for
some i, 1 = i = min(|x|, |y|) }.
For your PDA to work correctly it will need to be non-deterministic. You can
assume that you will always be given a valid string – that is, the input will always
contain one # and x and y will be strings over {a, b}. My PDA has 31 states and
and is broken into two major sections, one for |x| = |y| and one for |x| ? |y|.
For the case where we assume that |x| = |y|, you need to find a symbol that
matches at the same index of x and y (xi = yi for some i) and a symbol that does
not match at the same index of x and y (xj ? yj for some j). One way that this can
be accomplished is by finding an index i such that xi = yi and xi+1 ? yi+1 or xi+1 =
yi+1 and xi ? yi. As in programming assignment 3, you can store the index in the
stack and the values of xi and xi+1 in the state.
For the case where we assume that |x| ? |y|, you need to find an index i where
xi = yi. Since the lengths are different, we get that x ? y without finding an index j
in which xj ? yj. For this case, you can simple check that x1 = y1. If x1 ? y1, then
the other portion of the code (where we assume that |x| = |y|) will accept the
string.

Related Discussions:- Push down automata

Pendulum Swings, how many pendulum swings will it take to walk across the c...

how many pendulum swings will it take to walk across the classroom?

#dfa, Give DFA''s accepting the following languages over the alphabet {0,1}...

Give DFA''s accepting the following languages over the alphabet {0,1}: i. The set of all strings beginning with a 1 that, when interpreted as a binary integer, is a multiple of 5.

Universality problem, The Universality Problem is the dual of the emptiness...

The Universality Problem is the dual of the emptiness problem: is L(A) = Σ∗? It can be solved by minor variations of any one of the algorithms for Emptiness or (with a little le

Mapping reducibility, (c) Can you say that B is decidable? (d) If you someh...

(c) Can you say that B is decidable? (d) If you somehow know that A is decidable, what can you say about B?

Theorey Of Computation, program in C++ of Arden''s Theorem

program in C++ of Arden''s Theorem

Codds rule, What are codds rule

What are codds rule

Automaton for finite languages, We can then specify any language in the cla...

We can then specify any language in the class of languages by specifying a particular automaton in the class of automata. We do that by specifying values for the parameters of the

Give the acyclic paths through your graph, Give the Myhill graph of your au...

Give the Myhill graph of your automaton. (You may use a single node to represent the entire set of symbols of the English alphabet, another to represent the entire set of decima

Automata, automata of atm machine

automata of atm machine

Transition graph for the automaton, Lemma 1 A string w ∈ Σ* is accepted by ...

Lemma 1 A string w ∈ Σ* is accepted by an LTk automaton iff w is the concatenation of the symbols labeling the edges of a path through the LTk transition graph of A from h?, ∅i to

Write Your Message!

Captcha
Order Assignment

Featured Services

Order Now

Popular Subjects

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!

Submit Assignment

Academics

Major Subjects

Majors

Get In Touch

whatsapp: +91-977-207-8620

Phone: +91-977-207-8620

Email: [email protected]

TERMS & POLICIES

HELP & SUPPORT

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