Autor:

• Marcus Vinicius Midena Ramos

Editora Novatec
2021
ISBN 978-65-86057-59-1
336 páginas

Errata:

• Página 17: substituir por página 17 CORRIGIDA.
  
  Mudou o trecho "O livro de 2009..." até "...(o presente volume)."


• Página 36: substituir por página 36 CORRIGIDA.
  
  Mudou a Solução do Exercício 1.68.


• Página 69 (item 35): eliminar o parágrafo "A ideia aqui..." até "...um número ímpar." e também a gramática (regras 2.221 a 2.228), inserindo no lugar o que segue:
  
  Apesar de não ser muito intuitiva, uma gramática que gera esta linguagem é apresentada a seguir. O símbolo não-terminal T gera cadeias com uma quantidade par de símbolos a e também uma quantidade par de símbolos c, com símbolos b dentre eles. No entanto, esta geração é tal que os símbolos a e c comparecem aos pares da esquerda para a direita (quantidade par de um tipo, quantidade par do outro tipo etc). Para isso, T utiliza os símbolos não-terminais M (que gera uma quantidade par de símbolos a) e N (que gera uma quantidade de símbolos c). Os símbolos não-terminais P e Q geram, respectivamente, cadeias com um símbolo a seguido de um símbolo c e com um símbolo c seguido de um símbolo a. Dessa maneira, dois símbolos P ou dois símbolos Q ou um P e um Q ou ainda um Q e um P, nesta ordem, garantem que um símbolo a possa ser seguido por um símbolo c (ou vice-versa), mantendo o controle sobre a paridade destes símbolos. Ao final pode-se acrescentar um P ou Q, o que torna as quantidades de a e c ímpares. Ao término, deve-se acrescentar um a para que a quantidade de a seja par mantendo a quantidade de c ímpar. Outra maneira de fazer isso é não acrescentar nem P nem Q no final, mas um c para que a sua quantidade seja ímpar.
  
  Não se trata de uma gramática fácil de ser contruída ou entendida. Neste caso, é muito mais fácil produzir uma gramática linear à direita ou um autômato finito, respectivamente conforme a Solução do Exercício 3.25 (item 35) e a Solução do Exercício 3.82 (item 35). Esta gramática foi obtida a partir da gramática linear à direita da Solução do Exercício 3.25 (item 35).
  
  S -> XS (2.221')
  S -> Y (2.222')
  X -> TPTP (2.223')
  X -> TQTQ (2.224')
  X -> TPTQ (2.225')
  X -> TQTP (2.226')
  Y -> TPTWaW (2.227')
  Y -> TQTWaW (2.228')
  Y -> TWcW (2.229')
  T -> VT (2.230')
  T -> \epsilon (2.231')
  V -> M (2.232')
  V -> N (2.233')
  M -> WaWa (2.234')
  N -> WcWc (2.235')
  P -> WaWc (2.236')
  Q -> WcWa (2.237')
  W -> bW (2.238')
  W -> \epsilon (2.239')
  
  
• Página 89: substituir por página 89 CORRIGIDA.
  
  Mudou o enunciado do Exercício 3.56.


• Página 128 (item 35): eliminar o parágrafo "Basta gerar..." até "...símbolos c." e também a expressão regular, inserindo no lugar o que segue:
  
  Assim como a gramática apresentada na Solução do Exercício 2.44 (item 35), também não é fácil construir diretamente uma expressão regular que represente esta linguagem. A expressão regular apresentada a seguir foi obtida a partir de manipulação da gramática da Solução do Exercício 2.44 (item 35).
  
  A linguagem pode ser representada como:
  X*Y
  Substituindo X pela sua definição, obtemos:
  X = (TPTP+TQTQ+TPTQ+TQTP)
  (TPTP+TQTQ+TPTQ+TQTP)*Y
  Substituindo Y pela sua definição, obtemos:
  Y = (TPTb*ab*+TQTb*ab*+Tb*cb*)
  (TPTP+TQTQ+TPTQ+TQTP)*(TPTb*ab*+TQTb*ab*+Tb*cb*)
  Substituindo T pela sua definição, obtemos:
  T = (V*)
  ((V*)P(V*)P+(V*)Q(V*)Q+(V*)P(V*)Q+(V*)Q(V*)P)*((V*)P(V*)b*ab*+(V*)Q(V*)b*ab*+(V*)b*cb*)
  Substituindo V pela sua definição, obtemos:
  V = (M+N)
  (((M+N)*)P((M+N)*)P+((M+N)*)Q((M+N)*)Q+((M+N)*)P((M+N)*)Q+((M+N)*)Q((M+N)*)P)*(((M+N)*)P((M+N)*)b*ab*+((M+N)*)Q((M+N)*)b*ab*+((M+N)*)b*cb*)
  Substituindo M pela sua definição, obtemos:
  M = (b*ab*a)
  ((((b*ab*a)+N)*)P(((b*ab*a)+N)*)P+(((b*ab*a)+N)*)Q(((b*ab*a)+N)*)Q+(((b*ab*a)+N)*)P(((b*ab*a)+N)*)Q+(((b*ab*a)+N)*)Q(((b*ab*a)+N)*)P)*((((b*ab*a)+N)*)P(((b*ab*a)+N)*)b*ab*+(((b*ab*a)+N)*)Q(((b*ab*a)+N)*)b*ab*+(((b*ab*a)+N)*)b*cb*)
  Substituindo N pela sua definição, obtemos:
  N = (b*cb*c)
  ((((b*ab*a)+(b*cb*c))*)P(((b*ab*a)+(b*cb*c))*)P+(((b*ab*a)+(b*cb*c))*)Q(((b*ab*a)+(b*cb*c))*)Q+(((b*ab*a)+(b*cb*c))*)P(((b*ab*a)+(b*cb*c))*)Q+(((b*ab*a)+(b*cb*c))*)Q(((b*ab*a)+(b*cb*c))*)P)*((((b*ab*a)+(b*cb*c))*)P(((b*ab*a)+(b*cb*c))*)b*ab*+(((b*ab*a)+(b*cb*c))*)Q(((b*ab*a)+(b*cb*c))*)b*ab*+(((b*ab*a)+(b*cb*c))*)b*cb*)
  Substituindo P pela sua definição, obtemos:
  P = (b*ab*c)
  ((((b*ab*a)+(b*cb*c))*)(b*ab*c)(((b*ab*a)+(b*cb*c))*)(b*ab*c)+(((b*ab*a)+(b*cb*c))*)Q(((b*ab*a)+(b*cb*c))*)Q+(((b*ab*a)+(b*cb*c))*)(b*ab*c)(((b*ab*a)+(b*cb*c))*)Q+(((b*ab*a)+(b*cb*c))*)Q(((b*ab*a)+(b*cb*c))*)(b*ab*c))*((((b*ab*a)+(b*cb*c))*)(b*ab*c)(((b*ab*a)+(b*cb*c))*)b*ab*+(((b*ab*a)+(b*cb*c))*)Q(((b*ab*a)+(b*cb*c))*)b*ab*+(((b*ab*a)+(b*cb*c))*)b*cb*)
  Finalmente, substituindo Q pela sua definição, obtemos:
  Q = (b*cb*a)
  ((((b*ab*a)+(b*cb*c))*)(b*ab*c)(((b*ab*a)+(b*cb*c))*)(b*ab*c)+(((b*ab*a)+(b*cb*c))*)(b*cb*a)(((b*ab*a)+(b*cb*c))*)(b*cb*a)+(((b*ab*a)+(b*cb*c))*)(b*ab*c)(((b*ab*a)+(b*cb*c))*)(b*cb*a)+(((b*ab*a)+(b*cb*c))*)(b*cb*a)(((b*ab*a)+(b*cb*c))*)(b*ab*c))*((((b*ab*a)+(b*cb*c))*)(b*ab*c)(((b*ab*a)+(b*cb*c))*)b*ab*+(((b*ab*a)+(b*cb*c))*)(b*cb*a)(((b*ab*a)+(b*cb*c))*)b*ab*+(((b*ab*a)+(b*cb*c))*)b*cb*)
  

Para adquirir: Amazon ou Editora Novatec.

Dúvidas, críticas, erros ou sugestões? Envie um email para marcus (dot) ramos (at) univasf (dot) edu (dot) br