Solução: ((?:[A-Za-z]+\s+)+(?:[A-Za-z]+)).?(\d+/\d+/\d+).?((?:[\w]+\s+)+(?:[\w]+)).?(\d+).?(\d{5}[-.]?\d{3}).?((?:[\w]+\s+)+(?:[\w]+))
Explicação: ((?:[A-Za-z]+\s+)+(?:[A-Za-z]+)) < Aceita somente Letras, pois um nome não deve conter números É composto por Nome seguido de espaço e sobrenome, aceitando também nomes com mais de um sobrenome ex: Pedro Paulo de Oliveira.
.? << representa um separador, podendo existir ou não.
(\d+/\d+/\d+) << data em dia/mês/Ano ou mês/dia/ano (americano)
((?:[\w]+\s+)+(?:[\w]+)) << Mesmo sistema do nome, porém aceita números como ex: Rua 15 de Maio
(\d+) << número do endereço normal. Aceita qualquer quantidade de números.
(\d{5}[-.]?\d{3}) << cep brasileiro contendo 5 números seguidos de - ou ponto ou nada e 3 números.
((?:[\w]+\s+)+(?:[\w]+)) << Nome do estado. Poderia limitar apenas para letras.
obs: perceba que fiz grupos de grupos e escondi os subgrupos com ?: pois desta maneira aparece somente os grupos inteiros com a informação completa.
