Gramatica-Regular-e-Automato-Finito-Conversao-de-Linguagens-Formais

Considerando Σ a b e as especificações das linguagens abaixo para cada linguagem gere a respectiva gramática regular e usando a técnica de conversão gere o respectivo autômato finito a 25 Todas as palavras que começam com a e terminem com b b 25 Todas as palavras que começam e terminem com símbolos diferentes c 25 Todas as palavras que terminem com aba d 25 Todas as palavras em que toda posição ímpar é um a Observações Verifique se a linguagem aceita ou não a cadeia vazia Para cada linguagem acima inclua as derivações para duas cadeias uma que é gerada e outra que não é gerada Para cada linguagem você tem que entregar três coisas gramática autômato e derivações a S aA A aA bA b Três estados S inicial A qf estado final Temos as seguintes transições S a A A a A A b A A b qf Obtemos assim o seguinte autômato finito Cadeia aab Saab Aab Ab A qf aaba Saaba Aaba Aba Aa qfa A b S aA bB A aA bA b B aB bB a Quatro estados S inicial A B qf estado final Temos as seguintes transições S a A A a A A b A A b qf B a B B b B B a qf Obtemos assim o seguinte autômato finito Cadeia aab Saab Aab Ab A qf aaba Saaba Aaba Aba Aa qfa A c S aS bS aA A bB B a Quatro estados S inicial A B qf estado final Temos as seguintes transições S a S S b S S a A A b B B a qf Obtemos assim o seguinte autômato finito Cadeia aba Saba Sba Aba Sa Ba S A qf abb Sabb Sbb Abb Sb Bb S d I aP a P aI bI a b Quatro estados I inicial P qf estado final Temos as seguintes transições I a P I a qf P a I P b I P a qf P b qf Obtemos assim o seguinte autômato finito Cadeia aba Iaba qfba Pba qfa Ia P qf abb Iabb qfbb Pbb qfb Ib a S aA A aA bA b Três estados S inicial A qf estado final Temos as seguintes transições S a A A a A A b A A b qf Obtemos assim o seguinte autômato finito Cadeia aab Saab Aab Ab A qf aaba Saaba Aaba Aba Aa qfa A b S aA bB A aA bA b B aB bB a Quatro estados S inicial A B qf estado final Temos as seguintes transições S a A A a A A b A A b qf B a B B b B B a qf Obtemos assim o seguinte autômato finito Cadeia aab Saab Aab Ab A qf aaba Saaba Aaba Aba Aa qfa A c S aS bS aA A bB B a Quatro estados S inicial A B qf estado final Temos as seguintes transições S a S S b S S a A A b B B a qf Obtemos assim o seguinte autômato finito Cadeia aba Saba Sba Aba Sa Ba S A qf abb Sabb Sbb Abb Sb Bb S d I aP a P aI bI a b Quatro estados I inicial P qf estado final Temos as seguintes transições I a P I a qf P a I P b I P a qf P b qf Obtemos assim o seguinte autômato finito Cadeia aba Iaba qfba Pba qfa Ia P qf abb Iabb qfbb Pbb qfb Ib