Professor de Teoria da computação pediu um programa que deixe o usuário entrar com uma sequencia de letras, e o programa diz se a string digitada pertence a gramatica. To com dificuldade de pensar uma logica, alguém poderia ajudar?
A gramatica é essa, L(G) = {ab(n) a(m) b(m) | n >= 0 e m >= 1}
Uma gramática livre de contexto gera strings de uma linguagem livre de contexto. Um autômato de pilha reconhece strings de uma linguagem livre de contexto. Para o seu caso, basta implementar um reconhecedor usando uma pilha, simulando assim um autômato de pilha. Dividindo a string em duas partes, ab(n) e a(m) b(m), ab(n) é reconhecida facilmente, o “problema” é a segunda parte. Para cada a, empilhe algo. Ao terminar de reconhecer as, leia os bs e desempilhe. Se a pilha estiver vazia ao terminar o processamento da string, a string pertence à linguagem. Uma outra forma é simplesmente contar a quantidade de as e verificar se há a mesma quantidade de bs.
Sabe como posso implantar isso em java? qual método usar
Na linguagem no caso eu posso ter varios ababababab, ou 0 ab, assim como o “a” e o “b” podem aparecer uma vez ou varias, aaaaabbb, sou iniciante e to meio perdido em oq usar pra poder reconhecer isso
Cara… Vou fazer para você, mas se vc mostrar isso pro professor acho q ele vai se assustar. Enfim, uma gramática LL(1) para sua linguagem é algo como:
S -> "ab" AB T | T .
AB -> "ab" AB | .
T -> "a" F .
F -> T "b" | "b" .
Com uma gramática LL(1), vc consegue implementar um analisador sintático descendente recursivo com um símbolo de lookahead.
/**
*
* @author Prof. Dr. David Buzatto
*/
public class Parser {
private static final int EOF_CHAR = -1;
private enum Symbol {
a,
b,
ab,
EOF;
}
private class Token {
String texto;
Symbol symbol;
public Token( String texto, Symbol symbol ) {
this.texto = texto;
this.symbol = symbol;
}
@Override
public String toString() {
return texto;
}
}
private class Source {
String entrada;
int posicao;
Source( String entrada ) {
this.entrada = entrada;
}
int getChar() {
if ( posicao < entrada.length() ) {
return entrada.charAt( posicao );
}
return EOF_CHAR;
}
void avancar() {
if ( posicao < entrada.length() ) {
posicao++;
}
}
}
private class Scanner {
Source source;
String texto;
Symbol symbol;
Scanner( String entrada ) {
source = new Source( entrada );
}
void avancar() throws ParserException {
while ( source.getChar() == ' ' ) {
source.avancar();
}
texto = null;
if ( source.getChar() == EOF_CHAR ) {
symbol = Symbol.EOF;
} else {
if ( source.getChar() == 'a' ) {
source.avancar();
if ( source.getChar() == 'b' ) {
source.avancar();
texto = "ab";
symbol = Symbol.ab;
} else {
texto = "a";
symbol = Symbol.a;
}
} else if ( source.getChar() == 'b' ) {
source.avancar();
texto = "b";
symbol = Symbol.b;
} else {
throw new ParserException( "token desconhecido..." );
}
}
}
Token getToken() {
return new Token( texto, symbol );
}
}
private class ParserException extends RuntimeException {
public ParserException( String mensagem ) {
super( mensagem );
}
}
/**
* Gramática:
*
* S -> "ab" AB T | T .
* AB -> "ab" AB | .
* T -> "a" F .
* F -> T "b" | "b" .
*/
private Scanner scanner;
public Parser( String entrada ) {
scanner = new Scanner( entrada );
}
/**
* Analisa a produção S -> "ab" AB T | T .
*/
public void parseS() throws ParserException {
scanner.avancar();
if ( scanner.symbol == Symbol.ab ) {
scanner.avancar();
parseAB();
parseT();
if ( scanner.symbol != Symbol.EOF ) {
throw new ParserException( "\"EOF\" esperado..." );
}
} else if ( scanner.symbol == Symbol.a ) {
parseT();
if ( scanner.symbol != Symbol.EOF ) {
throw new ParserException( "\"EOF\" esperado..." );
}
} else {
throw new ParserException( "\"ab\" ou \"a\" esperado..." );
}
}
/**
* Analisa a produção AB -> "ab" AB | .
*/
public void parseAB() throws ParserException {
if ( scanner.symbol == Symbol.ab ) {
scanner.avancar();
parseAB();
}
}
/**
* Analisa a produção T -> "a" F .
*/
public void parseT() throws ParserException {
if ( scanner.symbol == Symbol.a ) {
scanner.avancar();
parseF();
} else {
throw new ParserException( "\"b\" esperado..." );
}
}
/**
* Analisa a produção F -> T "b" | "b" .
*/
public void parseF() throws ParserException {
if ( scanner.symbol == Symbol.a ) {
parseT();
if ( scanner.symbol == Symbol.b ) {
scanner.avancar();
} else {
throw new ParserException( "\"b\" esperado..." );
}
} else if ( scanner.symbol == Symbol.b ) {
scanner.avancar();
} else {
throw new ParserException( "\"b\" esperado..." );
}
}
public boolean parse() {
try {
parseS();
} catch ( ParserException exc ) {
return false;
}
return true;
}
public static boolean pertence( String s ) {
Parser p = new Parser( s );
return p.parse();
}
public static void main( String[] args ) {
String[] ss = {
"a b",
"aa bb",
"aaa bbb",
"aaaa bbbb",
"aaaaa bbbbb",
"ab a b",
"ab aa bb",
"ababab aaa bbb",
"abababab aaaa bbbb",
"ababababab aaaaa bbbbb",
"ab",
"abab",
"aa bbb",
"abab aa bbb",
"",
"abc",
"ab c",
"c aaa bbb",
"ab aaaa ab bbbb"
};
for ( String s : ss ) {
System.out.printf( "\"%s\": %s\n", s, Parser.pertence( s ) ? "SIM" : "NÃO" );
}
}
}
Algumas observações. A sua linguagem não especifica claramente se pode haver espaços entre os símbolos. Considerei o conjunto sigma sendo { “ab”, “a”, “b” }, podendo haver espacos. Com essa abordagem, uma implementação usando um reconhecedor é fácil fazer também. Se o seu alfabeto for somente “a” e “b”, o buraco é mais embaixo… Um reconhecedor vai ser não-determinístico. Um autômato de pilha não-determinístico pode ser um problema para converter para um determinístico para poder implementar. Uma outra abordagem é usar homomorfismo, convertendo a string para o alfabeto homomórfico, e fazendo o reconhecimento… Enfim, tem vários poréns. Não sei o que o seu professor quer com isso, se está esperando que vocês não consigam, se isso é um exercício… Dá para fazer, mas tem q pensar um pouco mais.
Pra ser bem sincero eu não entendi tudo, mas a ideia geral deu pra pegar, agr vou tentar estudar o código. E to no terceiro periodo da faculdade de T.I, mas acho q meu professor acha q ja estamos no ultimo kkk, esse é só um dos programas complicados que ele vive passando haha
Mas muito obrigado pela atenção Mestre
Pede pra ele fazer depois que tiver vencida a entrega da atividade 