How to set the Definition of Done of User Stories?

Agile teams tend to have a hard time while defining the Definition of Done - DoD of user stories (requirements).  The user requirements are defined, documented, approved and passed on to the development team for estimation and implementation (coding). But how can the agile team clearly state that they delivered what was defined on user stories?
The best way to accomplish this is by having user acceptance automated tests. Those tests can be written in the Gherkin language, forming a live and dynamic documentation. If a test fails, a requirement fails. If a test pass, it proves that the user story is complete and correctly implemented.
Delivering a requirement is demonstrating that it is working as expected and guaranteeing that the DoD has been fulfilled can be accomplished by having the acceptance tests passing.

Evolução (natural) do profissional de Software Quality Assurance

Automação de testes, BDD, TDD, ATDD, Agile, Integração contínua, Testes exploratórios e outras keywords não podem mais ser ignoradas pelos testadores; principalmente o fato de não saber ou não querer se envolver com programação. O testador que somente executa testes manualmente pode estar com seus dias contados ou perder muito em produtividade caso não se envolva com as mais novas práticas. Viemos para mostrar que fatores não técnicos como: coragem, atitude, pró-atividade, relacionamento interpessoal, respeito, motivação e trabalho em equipe são essenciais para um testador. Com esses fatores em prática, podemos nos nivelar e ganhar o respeito de desenvolvedores, designers, analistas de negócios e de outros testadores, levando-os a pensar em soluções com qualidade desde o início. Testar manualmente tem sido o mais comum, o de praxe, mantendo muitos testadores na ‘zona de conforto’; devemos quebrar esse paradigma e fazer com que a programação facilite nosso trabalho e faça com que testes manuais exerçam nossa criatividade, senso critico, detalhismo e nossa inteligência, deixando para que a máquina faça o trabalho repetitivo. Bem vindos à nova era do Software Quality Assurance.