RACSO
DFA
CFG
Operations:
Reg
,
CF
PDA
Reductions:
K
,
WP
,
CFG
,
NP
,
SAT
ANTLR:
lexical
,
syntactic
Exams
log in
,
register
,
become guest
This site uses cookies only for the purpose of identifying user sessions. This is required to properly register actions.
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
.