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

Finiteness problem for regular languages, The fact that the Recognition Pro...

The fact that the Recognition Problem is decidable gives us another algorithm for deciding Emptiness. The pumping lemma tells us that if every string x ∈ L(A) which has length grea

Computer achitecture, what is a bus and draw a single bus structure

what is a bus and draw a single bus structure

Class of local languages is not closed under union, Both L 1 and L 2 are ...

Both L 1 and L 2 are SL 2 . (You should verify this by thinking about what the automata look like.) We claim that L 1 ∪ L 2 ∈ SL 2 . To see this, suppose, by way of con

Dfa to re, c program to convert dfa to re

c program to convert dfa to re

Prism algorithm, what exactly is this and how is it implemented and how to ...

what exactly is this and how is it implemented and how to prove its correctness, completeness...

Ogdens lemma, proof ogdens lemma .with example i am not able to undestand ...

proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .

Path function of a nfa, The path function δ : Q × Σ* → P(Q) is the extensio...

The path function δ : Q × Σ* → P(Q) is the extension of δ to strings: This just says that the path labeled ε from any given state q goes only to q itself (or rather never l

Computation of a dfa or nfa, Computation of a DFA or NFA without ε-transiti...

Computation of a DFA or NFA without ε-transitions An ID (q 1 ,w 1 ) computes (qn,wn) in A = (Q,Σ, T, q 0 , F) (in zero or more steps) if there is a sequence of IDs (q 1

Brain game, If the first three words are the boys down,what are the last th...

If the first three words are the boys down,what are the last three words??

Local and recognizable languages, We developed the idea of FSA by generaliz...

We developed the idea of FSA by generalizing LTk transition graphs. Not surprisingly, then, every LTk transition graph is also the transition graph of a FSA (in fact a DFA)-the one

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