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

Overview of dfa, Explain Theory of Computation ,Overview of DFA,NFA, CFG, P...

Explain Theory of Computation ,Overview of DFA,NFA, CFG, PDA, Turing Machine, Regular Language, Context Free Language, Pumping Lemma, Context Sensitive Language, Chomsky Normal For

Decision Theroy, spam messages h= 98%, m= 90%, l= 80% non spam h=12%, m = 8...

spam messages h= 98%, m= 90%, l= 80% non spam h=12%, m = 8%, l= 5% The organization estimates that 75% of all messages it receives are spam messages. If the cost of not blocking a

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

Turing, turing machine for prime numbers

turing machine for prime numbers

Can you help me in automata questions, i have some questions in automata, c...

i have some questions in automata, can you please help me in solving in these questions?

9765432165, jhfsaadsa

jhfsaadsa

Research poster, RESEARCH POSTER FOR MEALY MACHINE

RESEARCH POSTER FOR MEALY MACHINE

Suffix substitution , Exercise Show, using Suffix Substitution Closure, tha...

Exercise Show, using Suffix Substitution Closure, that L 3 . L 3 ∈ SL 2 . Explain how it can be the case that L 3 . L 3 ∈ SL 2 , while L 3 . L 3 ⊆ L + 3 and L + 3 ∈ SL

Computer architecture, What are the issues in computer design?

What are the issues in computer design?

Codds rule, What are codds rule

What are codds rule

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