Formal Languages and Automata

Will somebody please help me with this problem? Yes, it is a homework problem, but I've been at it for days and am not making progress. Thanks /prog/

Prove L = {a^(n)b^(n) | n≥ 0} is a deterministic context-free language.

Make a grama fo it

>>2

I understand that making a grammar would prove that it's context-free, but that doesn't necessarily prove that it's deterministic does it? Is it even deterministic?

>>3
Sorry for rude post, it's been a while since I've been here and I forgot.

The grammar you're looking for is this:

S -> aSa | Λ

>>5 Ya, I realize that at this point. My problem isn't finding the grammar, it's proving that because I am able to represent it as a grammar, that it then means that the language is deterministic. I know how to prove it's context-free.

Thanks for trying though.

>>6
Make a deterministic pushdown automaton that parses it, what.

>>7

How does one do that? I know how to make pda's, but for this specific one, how do you build a deterministic one? At a certain point you will have two choices in a single state, whether to continue parsing a's, or to switch to parsing b's, making it non-deterministic.

>>6
Basically, >>7.

Q = {p,q,r}
SIGMA = {a,b}
GAMMA = {I,A}
F = {r}
Z = I
q0 = p
delta =
(p,a,I) -> (p,AI)
(p,a,A) -> (p,AA)
(p,epsilon,I) -> (q,I)
(p,epsilon,A) -> (q,A)
(q,1,A) -> (q,epsilon)
(q,epsilon,I) -> (r,I)

>>9
s/1/b/.

>>8
If you read an a, you push A on the stack and continue parsing them, if you read a b, you start parsing bs and pop the stack until there's nothing more to read and the top of the stack is I.

Great you now have a push down automaton. But now you have to prove that it really implements the a^n b^n grammar. You've just swapped a problem for an another problem..

Will you write out all sequences of a followed by b together with the state transitions they produce? I'm still convinced infinity does not exist no matter what http://dis.4chan.org/read/prog/1320862826/1-40 Jews tell me so it must be viable!