Resolvi publicar este problema proposto em sala de aula e que deixou muitos dos meus colegas com dúvidas a respeito.
O problema trata de simular o funcionamento dos autômatos abaixo e deve ser escrito em linguagem C.
A princípio parece complicado mas com uma análise atenciosa é possível resolvê-lo sem problemas.
Não há uma resposta única.
O passo a passo aqui apresenta uma solução possível.
O problema consiste em ler uma palavra que deve ser reconhecida por um dos autômatos acima a escolha do usuário.
Para começar é preciso ler uma cadeia de strings informada pelo usuário.
Isso resolve simplesmente com a função abaixo:
gets(palavra);
A variável palavra deve ser declarada como um tipo char.
O nome palavra foi usado para tornar fácil o entendimento, mas você pode dar qualquer nome para as suas variáveis.
Use a função abaixo para contar os caracteres da string e armazene o resultado em uma variável do tipo int:
int tamanho_string = strlen(palavra);
Você pode usar essa informação como referência para controlar o avanço de um contador em um loop enquanto estiver lendo cada caractere da string armazenada.
A string é armazenada em um vetor de uma linha com n posições. Cada posição do vetor recebe um caractere. O último caractere é sempre /0 (barra, zero). Este marcador especial delimita o fim da string no vetor. Ou seja, se você entrar com uma string de cinco caracteres, então ela será armazenada com o caractere especial e não terá cinco, e sim, seis caracteres. Mas não se preocupe, a função strlen conta os caracteres da sua string mas não inclui o caractere especial.
Você já leu a sua palavra e já contou quantos caracteres ela tem.
Agora precisamos criar uma rotina que deve percorrer a palavra da esquerda para a direita e verificar se os caracteres dela pertencem ao alfabeto dos autômatos.
Os autômatos deste problema possuem apenas 0 e 1 como caracteres válidos e não aceitam outros valores. Por isso é importante restringir esse detalhe criando uma regra que permita apenas aceitar caracteres 0 e 1 da sua string.
Crie um loop.
Ele pode ser do tipo while, do-while, ou for.
Em todos eles a rotina deve funcionar. Apenas certifique-se dos pontos a seguir.
Utilize a função abaixo para percorrer a sua palavra:
palavra[contador];
Você deve estar se perguntando para que serve esse contador.
Durante a rotina do loop criado por você, um contador deve ser posicionado ao final do loop para incrementar a contagem em +1.
A cada execução bem sucedida desse loop um incremento é feito e o loop será novamente executado até que se atinja a exceção ou condição especificada.
do{
rotina();
contador++;
}while(contador < tamanho_string);
No exemplo acima vemos o uso do loop com do-while.
O loop é executado e chama a função rotina. Logo após a execução de rotina, o contador é incrementado. A função rotina é apenas um exemplo.
Isso será feito até que o contador assuma o mesmo valor do tamanho da string. Nesse momento o loop interrompe sua execução.
Observe que o contador deve começar em zero. Por que?
Porque a string é um vetor. E a primeira posição de um vetor inicia-se em 0, e não em 1.
Lembre-se que estamos usando o contador para controlar o acesso à string da palavra. Portanto, palavra[0] significa que estamos lendo o primeiro caractere da palavra.
Outra forma de controlar o acesso aos caracteres da string é usar o loop não com um contador, e sim, verificando se o caractere pesquisado é /0.
do{
rotina();
}while(palavra[contador] != '/0');
A cada execução do bloco estará sendo verificado se o final da string foi alcançado.
Quando isso ocorrer, o bloco deixa de ser executado.
A função abaixo pode ajudar a identificar a validação do alfabeto dos autômatos durante a leitura dos caracteres da string:
if(palavra[contador] != '0' && palavra[contador] != '1'){
printf("Esta palavra tem um caractere diferente!");
}
else{
//Colocaremos algo aqui ainda. Mais adiante veremos isso!
}
Quando algum caractere diferente de 0 e 1 for lido uma mensagem será exibida identificando a ocorrência do erro.
O bloco else do exemplo acima receberá os detalhes descritos logo a seguir.
Agora só nos resta trabalhar as transições dos estados.
Use a função if para determinar as mudanças de estados:
if(palavra[contador] == '0'){
if(estado == 0){
printf("Transição: Q0 para Q1");
temp = 1;
}
if(estado == 1){
printf("Transição: Q1 para Q1");
temp = 1;
}
:
:
:
if(estado == 4){
printf("Transição: Q4 para Q4");
temp = 4;
}
}
No exemplo acima, referente ao primeiro autômato, estamos validando a condição de leitura para um caractere cujo valor é '0'.
Se isso for verdade, o bloco if será executado e entraremos em outros blocos if onde testaremos em qual estado do autômato estamos no momento.
No exemplo mostrado temos vários blocos if validando o estado.
Convencionou-se aqui que estado == 0 significa Q0, estado == 1 significa Q1, e assim por diante. Se quiser, você pode modificar seus próprios critérios. Mas não perca o raciocínio que estamos desenvolvendo aqui.
Cada estado terá sua respectiva transição e exibirá a devida mensagem. Na sequência, uma variável temporária armazena o estado para onde está ocorrendo a transição.
Após o bloco acima você deve repetí-lo mais uma vez. Dessa vez palavra[contador] == '1' e os blocos if internos devem ser atualizados de acordo com o diagrama do autômato apresentado no início desta postagem.
Note que '1' é diferente de 1.
O primeiro é um caractere - está entre aspas simples - e o outro é um inteiro.
Ao final dos dois blocos if maiores armazene o valor da variável temporária na variável estado.
Com isso você atualiza o estado atual de transição.
Por que ao final dos blocos? A atualização poderia ser feita dentro do próprio bloco?
Se ao invés da variável temporária nós atualizássemos a própria variável estado correríamos um sério risco na leitura dos próximos blocos e encontraríamos um bloco que leria o estado atual modificado, consequentemente ele executaria o bloco e modificaria o estado de transição, outra vez.
E não queremos isso! Só podemos executar uma transição a cada caractere lido!
Agora seu loop está completo!
Para finalizar o nosso trabalho devemos validar o estado atual ao final da leitura da string.
Crie um bloco if para verificar o valor de estado.
Dependendo do valor determine se é um estado final, porque se assim o for a string lida deve ser aceita. O contrário disso deve ser recusada.
Estamos praticamente terminados.
Exceto pela validação da palavra vazia. Ainda falta esta criança!
Concorda que todo este trabalho que tivemos só tem sentido se tivermos uma string com valores?
gets(palavra) permite o armazenamento de uma string vazia simplesmente pressionando a tecla Enter sem que você digite alguma coisa antes.
Como resolver este impasse?
Se você pensou em um bloco if para validar o tamanho da sua string, acertou!
if(tamanho_string == 0){
printf("Temos uma palavra vazia!");
}
else{
Coloque o seu loop aqui!
}
Se você seguiu corretamente as dicas até aqui seu programa em C deve funcionar.
Boa sorte!
Eduardo Viana
Editor do site Conectado+
Nenhum comentário:
Postar um comentário