Exercise 1 | RACSO

Exercise 1_›:

Deterministic uniquely-accepting PDA for

\{ a^n b^n \mid n\geq 0 \}

Write a deterministic uniquely-accepting PDA recognizing the language over

\{a,b\}

where the first half of each word only contains

a

’s and the second half only contains

b

’s.

Authors: Guillem Godoy / Documentation:

// In the first problem on PDAs we directly propose a solution,
// in order to show which is the syntax to represent PDAs. You
// just have to uncomment (remove //) the following seven lines
// and submit:
//
//   Z q0 q0 q3
//   Z q0   -> Z  q1
//   Z q1 a -> ZA q1
//   A q1 a -> AA q1
//   A q1 b ->    q2
//   A q2 b ->    q2
//   Z q2   -> Z  q3
//
// The first line specifies the initial stack symbol (Z), the
// initial state (q0) and, finally, the list of accepting states
// (q0 and q3). Each of the following lines represents a
// transition of the automaton. At the left-hand side of the
// symbol -> we have the top of the stack, the state and,
// optionally, an input symbol. At the right-hand side of -> we
// have the contents that will be pushed to the stack (possibly
// empty) and the state reached. For instance, a transition like
//    Z q0 a -> ZA q1
// would be executed from state q0, popping the symbol 'Z' from
// the stack, reading the symbol 'a' from the input, pushing ZA
// onto the stack (the symbol 'A' would be at the top) and also
// changing into state q1.
// Transition rules can also be written more compactly when
// several rules share the same origin state and the same destiny
// state. Using this idea for all rules, the previous automaton
// can be equivalently written of the form:
//
//   Z q0 q0 q3
//   q0 -> Z |Z         -> q1
//   q1 -> Za|ZA, Aa|AA -> q1
//   q1 -> Ab|          -> q2
//   q2 -> Ab|          -> q2
//   q2 -> Z |Z         -> q3

To be able to submit you need to either log in, register, or become a guest.

Exercise 1›:

Exercise 1_›: