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

Automata, automata of atm machine

automata of atm machine

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

program in C++ of Arden''s Theorem

Notes, write short notes on decidable and solvable problem

write short notes on decidable and solvable problem

IT PRoject Management, What are the benefits of using work breakdown struct...

What are the benefits of using work breakdown structure, Project Management

CNF, S-->AAA|B A-->aA|B B-->epsilon

S-->AAA|B A-->aA|B B-->epsilon

Qbasic, Ask question #Minimum 100 words accepte

Ask question #Minimum 100 words accepte

Turing machine, explain turing machine .

explain turing machine .

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

Vogel Approximation Method(VAM, how to write program Minimum Cost Calculat...

how to write program Minimum Cost Calculation - Vogel Approximation Method(VAM

Construct a recognizer, Let L1 and L2 be CGF. We show that L1 ∩ L2 is CFG t...

Let L1 and L2 be CGF. We show that L1 ∩ L2 is CFG too. Let M1 be a decider for L1 and M2 be a decider for L2 . Consider a 2-tape TM M: "On input x: 1. copy x on the sec

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: +1-415-670-9521

Phone: +1-415-670-9521

Email: [email protected]

TERMS & POLICIES

HELP & SUPPORT

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