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

Binary form and chomsky normal form, Normal forms are important because the...

Normal forms are important because they give us a 'standard' way of rewriting and allow us to compare two apparently different grammars G1  and G2. The two grammars can be shown to

Regular expression, what is regular expression?

what is regular expression?

Grammer, write grammer to produce all mathematical expressions in c.

write grammer to produce all mathematical expressions in c.

Automata and compiler, Automata and Compiler (1) [25 marks] Let N be the...

Automata and Compiler (1) [25 marks] Let N be the last two digits of your student number. Design a finite automaton that accepts the language of strings that end with the last f

Production, How useful is production function in production planning?

How useful is production function in production planning?

Perfect induction, A.(A+C)=A

A.(A+C)=A

Find regular grammar : a(a+b)*(ab*+ba*)b, Find the Regular Grammar for the ...

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

Project Management at the Phoenician, Ask question #Minimum 20 words accept...

Ask question #Minimum 20 words accepted#

Myhill-nerode, Theorem (Myhill-Nerode) A language L ⊆ Σ is recognizable iff...

Theorem (Myhill-Nerode) A language L ⊆ Σ is recognizable iff ≡L partitions Σ* into ?nitely many Nerode equivalence classes. Proof: For the "only if" direction (that every recogn

Union, Intuitively, closure of SL 2 under intersection is reasonably easy ...

Intuitively, closure of SL 2 under intersection is reasonably easy to see, particularly if one considers the Myhill graphs of the automata. Any path through both graphs will be a

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