TRABALHO DE COMPILADORES

Prévia do material em texto

Índice
1.	Introdução	1
1.1.	Objectivo Geral	1
2.	Teoria Das Linguagens Formais e Autônomas	2
2.2.	Conceitos e Fundamentos sobre Teoria das Linguagens Formais e Autônomas	3
2.3.	Símbolos e Cadeias	4
2.4.	Relação Entre a Linguagem Formal e a Matemática Discreta	5
3.	Teoria da Computação	7
3.1.	Temas-chave da Teoria da Computação	12
4.	Algoritmo de Markov	14
4.1.	Processo Estocástico no Algoritimo de Markov	15
4.2.	Processos Markovianos	16
4.3.	Simulação De Uma Cadeia De Markov	17
5.	Gramáticas De Chomsky	18
5.1.	A Revolução De Chomsky: Do Estruturalismo Ao Gerativismo	18
5.2.	Linguística Contemporânea e Gramática Tradicional	19
5.3.	O Estruturalismo E O Behaviorismo	20
5.4.	Chomsky em Transição	21
5.5.	A Primeira Gramática De Chomsky	22
6.	Referência Bibliográficas	26
1. Introdução
O presente trabalho foi constituído de maneira a englobar temas importantes, acasalando-as nos apresenta uma visão sobre os compiladores. 
Certamente que no mundo da computação entender o funcionamento dos compiladores torna-se uma tarefa importante, porque melhor se poderá compreender a comunicação entre as maquinas e a linguagem humana. 
Nesta lógica de ideia, a fim do dar uma pequena percepção, dos fundamentos que constituem os compiladores, neste trabalho serão abordados temas como:
· Teoria das Linguagens Formais e Autómatos;
· Propósitos da Teoria da Computação;
· Algoritmos de Markov;
· Gramáticas de Chomsky.
Esperemos que o caro leitor consultando este material acadêmico poderá ter uma mínima visão sobre os fundamentos dos compiladores através dos temas acima mencionados.
1.1. Objectivo Geral	
Ao final deste capítulo você deverá ser capaz de: 
· Entender o que é a Teoria das Linguagens Formais e Autómatos e como funciona;
· Conhecer o Propósitos da Teoria da Computação;
· Compreender como funciona o Algoritmos de Markov;
· Conhecer a essência da Gramáticas de Chomsky;
· Ter uma visão básica sobre os compiladores.
2. Teoria Das Linguagens Formais e Autônomas
Nesta secção apresentaremos os principais conceitos básicos associados ao estudo de linguagens, como é o caso dos símbolos, das cadeias e das linguagens propriamente ditas, assim como dos métodos empregados para a formalização das linguagens, como é o caso das gramáticas e dos reconhecedores e a importância das mesmas. 
As gramáticas possuem grande importância na análise e na especificação formal da sintaxe de linguagens, principalmente das linguagens de programação, ao passo que os reconhecedores definem modelos que servem como base para a construção de analisadores léxicos e sintáticos nos compiladores e interpretadores de tais linguagens. Na prática, o estudo sistemático das linguagens formais e dos autômatos viabilizou o desenvolvimento de técnicas eficientes para a utilização econômica das linguagens de programação, originando-se em seu estudo grande parte do interesse que recai sobre os assuntos ligados a esse tema.
2.1. Breve Historial
Atualmente, há entre 3 000 e 6 000 línguas usadas pela espécie humana, e um número muito maior era usado no passado. As línguas naturais são os exemplos mais marcantes que temos de linguagem. Outros tipos de linguagem se baseiam na observação visual e auditiva, como as línguas de sinais e a escrita. Os códigos e outros sistemas de comunicação construídos artificialmente, como aqueles usados para programação de computadores, também podem ser chamados de linguagens. Nesse sentido, linguagem pode ser considerado um sistema de sinais para codificação e decodificação de informações, isto é, um sistema que permite a comunicação.
Uma linguagem se baseia em um diversificado sistema de regras relativas a símbolos para os seus significados, resultando em um número indefinido de possíveis expressões inovadoras a partir de um finito número de elementos.
No contexto tecnológico, considera-se a linguagem artificial, é um tipo de linguagem onde a gramática ou vocabulário foram conscientemente concebidos ou modificados por um indivíduo ou grupo, em vez de evoluído naturalmente. Existem várias razões possíveis para a construção de uma língua, facilidade humana para a comunicação, adição de profundidade a uma obra de ficção ou a lugares imaginários, experimentação linguística, criação artística ou, ainda, realização de jogos de linguagem.
A matemática, a lógica e a ciência da computação utilizam entidades artificiais chamadas linguagens formais incluindo a linguagem de programação e a linguagem de marcação.
2.2. Conceitos e Fundamentos sobre Teoria das Linguagens Formais e Autônomas
Para definir o que é a teoria das linguagens formais é preciso definir o que é linguagem e o que é linguagem formal. Inicialmente, de maneira bastante informal, podemos definir uma Linguagem como sendo uma forma de comunicação. Elaborando um pouco mais esta definição, podemos definir uma linguagem como sendo um conjunto de elementos ou símbolos e um conjunto de métodos ou regras para combinar estes elementos, usado e entendido por uma determinada comunidade. São exemplos as linguagens naturais ou idiomas, linguagens de programação e os protocolos de comunicação.
Podemos dizer que linguagens formais são mecanismos formais para representação e especificação de linguagens, baseados na chamada teoria da computação. De forma especifica entende-se como o estudo de modelos matemáticos que possibilitam a especificação e o reconhecimento de linguagens aplicáveis na computação, suas classificações, estruturas, propriedades, características e inter-relacionamentos.
As representações podem ser feitas por reconhecedores e geradores. Os reconhecedores são dispositivos formais que servem para verificar se uma frase pertence ou não à determinada linguagem, estes são chamados de autômatos: autômatos finitos, autômatos de pilha e máquina de Turing. 
Os sistemas geradores são dispositivos formais que permitem a geração sistemática de todas as frases de uma linguagem. Os principais sistemas geradores disponíveis são as gramáticas, onde se destacam as gramáticas de Chomsky. Então, linguagens formais podem ser representadas de maneira finita e precisa através de sistemas com sustentação matemática.
Assim a teoria das linguagens formais, geralmente se preocupa com linguagens formais que são descritas por algumas regras sintáticas. Na prática, há muitas línguas que podem ser descritas pelas regras, tais como linguagens regulares e linguagens livres de contexto. A noção de uma gramática formal pode estar mais perto do conceito intuitivo de uma linguagem, que é descrita por regras sintáticas. 
A importância dessa teoria na ciência da computação é dupla: ela tanto apoia outros aspectos teóricos da ciência da computação.
Decidibilidade, contabilidade, complexidade computacional, por exemplo, como fundamenta diversas aplicações computacionais tais como processamento de linguagens, reconhecimento de padrões, modelagem de sistemas.
Não podemos avançar sem apresentar alguns conceitos sobre os símbolos e cadeias.
2.3. Símbolos e Cadeias 
Os símbolos, também denominados palavras ou átomos, são representações gráficas, indivisíveis, empregadas na construção de cadeias. Estas são formadas através da justaposição de um número finito de símbolos, obtidos de algum conjunto finito não-vazio, denominado alfabeto. Cada símbolo é considerado como uma unidade atômica, não importando a sua particular representação visual. 
São exemplos de símbolos: a, abc, Begin, if , 5, 1024, 2.017e4; 
Perceba-se que não há uma definição formal para “símbolo”. Deve-se intuir o seu significado como entidade abstrata, e dessa forma aceitá-lo como base para a teoria que será desenvolvida. Pode-se dizer que se trata de um conceito primitivo.
O comprimento de uma cadeia é um número natural que designa a quantidade de símbolos que a compõem. O comprimento de uma cadeia α é denotado por |α|. 
Exemplo 1.1: Considerem-se as cadeias α = 1, β = 469, χ = ble60, φ = df. Então, |α| = 1, |β| = 3, |χ| = 5 e |φ| = 2.
 	O comprimento de uma cadeia é um número natural que designa a quantidade de símbolos que a compõem. Ocomprimento de uma cadeia α é denotado por |α|.
 	Exemplo 1.2: Considerem-se as cadeias α = 1, β = 469, χ = ble60, φ = df. Então, |α| = 1, |β| = 3, |χ| = 5 e |φ| = 2. 
Dá-se o nome de cadeia elementar ou unitária a qualquer cadeia formada por um único símbolo, como é o caso da cadeia α.
 Exemplo 1.3: Naturalmente, toda cadeia unitária tem comprimento 1.
Um outro importante exemplo de alfabeto corresponde ao conjunto dos símbolos definidos em algum dicionário da língua portuguesa. Note que, diferentemente do alfabeto Σ anteriormente considerado, em que todos os símbolos eram compostos de um único caractere, os símbolos deste novo alfabeto são construídos a partir da concatenação de um número variável de caracteres no caso, as letras do alfabeto romano. Para o presente estudo, embora representados com diversos caracteres, tais símbolos são considerados indivisíveis, e as correspondentes cadeias elementares apresentam, por essa razão, comprimento unitário quando consideradas no contexto da língua portuguesa.
 	Considerando-se ainda que tal alfabeto é suficientemente extenso para conter as conjugações de todos os verbos, as formas flexionadas de todos os adjetivos, substantivos etc, enfim, todas as palavras possíveis de serem empregadas em nosso idioma, então a cadeia, exemplo de uma cadeia no novo alfabeto deverá ser considerada uma cadeia válida, construída a partir dos símbolos desse alfabeto, e o seu comprimento é igual a 7.
 	Note que esse alfabeto da língua portuguesa, apesar de extenso, é finito, e também que é possível construir uma quantidade infinita de cadeias de comprimento finito com os símbolos dele. Observe-se que, entre estas, há cadeias que na língua portuguesa não fazem sentido. Por exemplo, cadeia um exemplo errado o. As demais são empregadas nas diversas formas de comunicação humana. 
O conceito de cadeia vazia é especialmente importante na teoria das linguagens formais. Denota-se por cadeia formada por uma quantidade nula de símbolos, isto é, a cadeia que não contém nenhum símbolo. Formalmente, |ǫ| = 0.
2.4. Relação Entre a Linguagem Formal e a Matemática Discreta
As linguagens formais ou linguagens estruturadas em frases podem ser vistas como conjuntos. Consequentemente, muito da teoria e dos principais resultados da área de linguagens formais está baseado na ainda mais fundamental teoria dos conjuntos da matemática discreta.
Além das linguagens formais, teoria, modelagem e implementação das operações previamente definidas para conjuntos, como união, diferença, intersecção etc. Outras operações, tais como a concatenação e os fechamentos, também são fundamentais para a definição e o estudo das linguagens formais.
A teoria dos conjuntos é relativamente extensa, e dela serão apresentados neste capítulo apenas os tópicos, conceitos e definições que se mostram mais importantes para a fundamentação e o estudo dos capítulos seguintes.
3. 
Teoria da Computação 
A teoria da computação é um subcampo da ciência da computação e matemática que busca determinar quais problemas podem ser computados em um dado modelo de computação. A computação pode ser definida como a solução de um problema ou, formalmente, o cálculo de uma função por meio de um algoritmo. Apesar de intuitivo na história humana, o conceito de execução de uma tarefa com passos finitos a fim de se obter um resultado, ou seja, um algoritmo, não possuía uma definição formal até a conceituação do modelo de Máquina Universal de Turing. 
A teoria da computação teve início nos primeiros anos do século XX, antes da invenção dos modernos computadores eletrônicos. Naquela período, após a famosa palestra do matemático alemão David Hilbert em que ele listou os maiores desafios no campo da matemática para o século vindouro, os matemáticos se debruçavam sobre o décimo problema de Hilbert tentando descobrir quais problemas matemáticos poderiam ser resolvidos por um método efetivo, e quais não poderiam. O primeiro passo estava em definir o significado de um método efetivo para resolver o problema. Em outras palavras, eles precisavam de um modelo formal da computação.
Diversos modelos diferentes da computação foram propostos pelos primeiros pesquisadores. Um modelo, conhecido como máquina de turing, propunha a construção de uma máquina universal, capaz de operar com uma sequência de instruções e dados entremeados em uma fita de comprimento infinito; a máquina poderia operar em um ponto da fita de cada vez utilizando um cabeçote de leitura e escrita, executando assim a programação que lhe fosse passada. Outro modelo se baseia em funções recursivas compostas para operar diretamente sobre os números. Uma abordagem similar é o cálculo lambda. Outra classe de abordagens trabalha com regras gramaticais operando sobre cadeias de caracteres, como é o caso dos cadeias de Markov e dos sistemas de Post.
Todos os formalismos propostos acima são equivalentes em termos de poder computacional, ou seja, qualquer computação que possa ser realizada com um modelo pode ser realizada com qualquer um dos outros modelos. Ainda em termos teóricos, os modelos propostos são equivalentes aos computadores eletrônicos, desde que não haja restrições de memória envolvidas. Na verdade, acredita-se que todas as formalizações teoricamente possíveis para o conceito de algoritmo são equivalentes em poder a uma máquina de Turing; esta é a tese de Church-Turing. As questões relativas à possibilidade de realizar certos tipos de computação em determinados tipos de máquina ou formalismo teórico são investigadas pela teoria da computabilidade.
A teoria da computação estuda os modelos de computação genéricos, assim como os limites da computação:
· Quais problemas jamais poderão ser resolvidos por um computador, independente da sua velocidade ou memória? Quais problemas podem ser resolvidos por um computador, mas requerem um período tão extenso de tempo para completar a ponto de tornar-se a solução impraticável? 
· Em que situações pode ser mais difícil resolver um problema do que verificar cada uma das soluções manualmente? (Ver Classes P e NP).
Em geral, as questões relativas aos requerimentos de tempo ou espaço memória, em particular de problemas específicos são investigadas pela teoria da complexidade computacional.
Além dos modelos genéricos de computação, alguns modelos computacionais mais simples são úteis para aplicações mais restritas. Expressões regulares, são por exemplo utilizadas para especificar padrões de cadeias de caracteres, sendo populares em aplicações UNIX e em algumas linguagens de programação, como Perl e Python. Outro formalismo matematicamente equivalente às expressões regulares são os autômatos finitos, que são utilizados em desenho de circuitos e em alguns sistemas de resolução de problemas. As gramáticas livres de contexto são utilizadas para especificar a sintaxe das linguagens de programação; um formalismo equivalente, são os autômatos com pilha, ou pushdown automata. As funções recursivas primitivas formam uma subclasse das funções recursivas.
Modelos de computação diferentes podem realizar tarefas distintas. Uma forma de estudar o poder de um modelo computacional é estudar a classe das linguagens formais que o modelo pode gerar; o resultado é a hierarquia de Chomsky das linguagens.
As tabelas abaixo mostram algumas das classes de problemas ou linguagens, gramáticas que são consideradas em teoria da computabilidade azul e em teoria da complexidade vermelho. Se a classe X é um subconjunto propriamente contido em Y, então X é mostrado abaixo de Y, conectados por uma linha escura. Se X é um subconjunto, mas não é sabido se os conjuntos são iguais ou não, então a linha que os conecta será mais clara e pontilhada.
O termo computação costuma ser empregado para designar o uso de algoritmos para a resolução de problemas. Como se diz formalmente, esse vocábulo alude à execução de algoritmos como meio para realizar o cálculo de funções. Foi praticada por milênios no passado, mentalmente ou por escrito, muitas vezes com o auxílio de tabelas. Ramo da matemática e daciência da computação, a teoria da computação surgiu no princípio do século XX, antes da invenção dos computadores, e estuda modelos formais de computação, sua aplicabilidade e sua viabilidade prática à resolução revista de computação e tecnologia da PUC-SP — Departamento de Computação/FCET/PUC-SP ISSN 2176-7998 Vol. I No. 1. Desse estudo emergiram propostas, na forma de diferentes modelos de computação, representados através de diversificadas abstrações, apresentadas em variadas notações. Segundo a conjuntura denominada tese de Turing-Church, todos esses modelos se equiparam uns aos outros quanto ao seu poder computacional, além de serem todos também equivalentes a um computador hipotético que oferecesse uma disponibilidade ilimitada de memória: 
• A máquina de turing, que foi proposta como modelo universal de computação, e trabalha com operadores muito rudimentares sobre instruções e dados gravados em uma fita de trabalho de comprimento infinito. Dos modelos universais de computação existentes, talvez seja o mais conhecido e famoso, e é bastante aderente ao estilo de programação representado pelo paradigma imperativo; 
• O cálculo lambda, formalismo que foi proposto e empregado na representação de programas desenvolvidos segundo o paradigma de programação adotado pelas linguagens funcionais, e que se mostra muito adequado para a representação formal de fenômenos computacionais ligados a linguagens de programação declarativas; 
• As Funções recursivas, utilizadas em matemática desde épocas muito anteriores à dos computadores, podem também servir como um modelo computacional inspirado naquela ciência, e, ao contrário da maioria dos outros modelos em uso, têm a grande vantagem de permitir a representação e a manipulação direta de valores numéricos; 
• As Gramáticas Gerativas, permitem a representação de linguagens através do uso de regras de substituição, que operam sobre sequências de símbolos, sendo muito empregadas na especificação e na representação de linguagens artificiais, como as de programação e de outras notações constituídas de cadeias de caracteres com lei de formação conhecida, tornando natural a formalização e a manipulação algorítmica de textos simbólicos. 
• Os Dispositivos adaptativos, particularmente aqueles baseados em autômatos, são modelos de computação capazes de representar fenômenos computacionais complexos através de quaisquer abstrações cujo comportamento seja descrito através de um conjunto de regras dinamicamente variável. Essa dinâmica se obtém associando se à aplicação de cada regra uma ação que especifica alterações a serem realizadas sobre o conjunto de regras. Assim, ao executarem essas ações adaptativas, tais dispositivos podem ir alterando, de forma autônoma, seu próprio comportamento, em função do seu histórico de funcionamento. 
Com isso, um dispositivo adaptativo torna-se equivalente à máquina de Turing, portanto poderá representar o conhecimento adquirido em sua operação, tendo, no entanto, sobre a máquina de Turing, nesse aspecto, a vantagem de concentrar, de forma localizada, em seu próprio conjunto de regras, a representação de tal conhecimento. Assim, torna-se possível identificar e acompanhar até mesmo de forma incremental a aquisição do conhecimento por um dispositivo adaptativo, através da inspeção do seu conjunto de regras e da sua variação toda vez que, durante sua operação, alguma ação adaptativa for executada. Por essa e diversas outras razões, os dispositivos adaptativos têm sido considerados como alternativas atraentes para a representação de fenômenos de aprendizagem, na área de inteligência artificial. 
• Muitos outros modelos de computação têm sido propostos e podem ser encontrados com facilidade na literatura, entre os quais podem ser destacados: os Sistemas de Post, as Cadeias de Markov, as máquinas de Mealy e de Moore, diversas outras variantes das máquinas de estados, dos autômatos e transdutores finitos e de pilha, máquinas de turing universais, máquinas virtuais diversas, utilizadas na execução de diversas linguagens de programação P-system, Java byte-code, etc, Redes de Petri, Statecharts, máquinas probabilísticas, e inúmeras outras.
 
A Teoria da Computabilidade investiga a possibilidade de máquinas computacionais e de certos formalismos teóricos adotados como modelos de computação apresentarem ou não a capacidade de realizarem automaticamente determinados tipos de computação. Em termos do que se conhece hoje dos computadores e da computação, uma versão dessa investigação pode ser traduzida na busca de respostas para a pergunta seguinte: é possível ou não construir um algoritmo capaz de resolver de forma automática um dado problema através da execução iterativa de passos de instruções em um dado dispositivo computacional, como, por exemplo, um computador digital ou algum outro modelo computacional? Mais abrangente, a teoria da computação propõe, estuda e compara modelos de computação, as classes de problemas que cada um deles consegue resolver e os limites a que cada qual está sujeito. Ilustrando, podem ser citados alguns problemas para os quais é impossível criar programas de computador que lhes sirvam de solução. São esses os problemas ditos incomputáveis, entre os quais se destacam: o problema da parada da máquina de turing; 
Problemas incomputáveis existem, mas felizmente constata-se a existência de outra infinidade de problemas computáveis, de grande importância prática, e isso motiva o seu estudo, do ponto de vista tanto teórico como prático. 
Dos problemas computáveis, alguns se mostram impraticáveis por exigirem um tempo abusivo ou uma quantidade de memória excessiva para sua operação. Para os decidíveis é possível a construção de algoritmos que sempre terminam, quaisquer que sejam os dados a eles fornecidos. Para os inelidíveis, é possível elaborar procedimentos computacionais, porém estes terminam somente quando se lhes apresentam dados “corretos”, aderentes ao que normalmente se espera, podendo, no entanto, iniciar um ciclo infinito de execução em resposta aos demais dados. O estudo da decidibilidade de algoritmos data dos anos 1930, quando os estudiosos da área tentavam demonstrar ser inviável realizar raciocínios matemáticos com a ajuda de dispositivos automáticos. Um interessante problema nessa área é o das provas automáticas dos teoremas de uma dada teoria. É possível provar que o excessivo tempo de resposta de provadores de teoremas para determinadas teorias torna impraticável seu uso com fórmulas grandes. 
É o caso da aritmética de Presburger, que se mostra decidível, porém duplamente exponencial em complexidade. Nos casos de problemas de alta complexidade computacional, pode ser interessante determinar para quais situações vale a pena desenvolver uma solução algorítmica e para as quais outras é mais conveniente efetuar verificações extensivas de propostas de solução. O estudo das classes P e NP de complexidade computacional costuma analisar famílias de problemas que ilustram bem esta situação. Se de um lado a teoria da computação busca soluções gerais e grandiosas para classes amplas de problemas, por outro lado ocupa-se também de determinar modelos de complexidade mínima que resolvam satisfatoriamente situações menos gerais, de interesse prático. 
3.1. Temas-chave da Teoria da Computação 
Permeando todos os estudos relacionados com os aspectos teóricos da Computação, encontram-se os assuntos usualmente conhecidos como matemática discreta e lógica matemática. Truss afirma que, independentemente de eventuais aplicações, somente por sua complexidade e beleza a matemática já é em si própria fascinante e significativa, merecendo atenção e estudo. Diz também ser um verdadeiro prêmio o fato de a matemática ser também útil, embora isso decorra da compreensão profunda da lógica e elegância subjacentes. Completa sugerindo que não se veja a matemática como uma coleção complicada e incompreensível de abstrações, mas como um interessante e prazeroso tema de estudo, vivo e poderoso. Entre os tópicos mais comumente estudados da teoriada computação, merecem destaque particular os seguintes: Revista de Computação e Tecnologia da PUC.
• Matemática discreta, teoria dos grafos, teoria dos conjuntos e teoria das funções recursivas; 
• Linguagens formais e autômatos; 
• Máquinas universais, computabilidade, algoritmos; 
• Complexidade, intratabilidade; 
• Máquinas fin itas sequenciais com entrada e saída, transdutores, máquinas de Mealy e de Moore; 
• Lógica matemática, gramáticas formais, modelos matemáticos, teoremas; 
• Aspectos teóricos subjacentes a redes neurais, computação evolutiva e sistemas nebulosos. Além de darem uma visão que permite avaliar o alcance e as limitações dos computadores, uma observação menos superficial permite assegurar que, longe do que seria intuitivo, as complexas estruturas conceituais estudadas na Teoria da Computação gozam, na prática, de uma extraordinária aplicabilidade. Assim, as ferramentas conceituais oferecidas pela teoria viabilizam a obtenção de soluções para muitos complexos problemas da prática, e apontam formas elegantes e econômicas para a realização tecnológica de tais soluções. Destacam-se, entre muitos outros, os seguintes casos ilustrativos: 
• A álgebra booleana e a teoria das máquinas sequenciais fornecem um substrato conceitual essencial para a descrição de muitos fenômenos computacionais, sendo em particular extensivamente utilizadas no projeto lógico de computadores e de sistemas digitais em geral, de codificadores, de sistemas de comunicação, de controladores e de robôs; 
• A teoria das relações e a álgebra relacional constituem fundamentos teóricos nos quais se baseiam muitas técnicas e métodos hoje disponíveis, que nas aplicações práticas proporcionam formas metódicas e muito adequadas para a formulação rigorosa e confiável de sistemas de software que operam sobre complexos bancos de dados; 
• Autômatos, transdutores e outras máquinas de estados clássicas, formuladas com base em estados internos, funções de transição e funções de saída, têm auxiliado significativamente na elaboração de pré-processadores, de compiladores, e no processamento simbólico de cadeias de símbolos. Essas abstrações constituem o alicerce de inúmeros softwares, de interfaces entre o ser humano e os computadores, em particular os de acesso às redes de computadores, de processos de automação industrial e de protocolos de comunicação digital.
4. 
Algoritmo de Markov
A própria natureza dos cálculos em probabilidade nos conduz ao questionamento se existe ou não dependência na ocorrência de fenômenos simultâneos ou sucessivos. Será que ao retirarmos sucessivamente duas bolas de uma urna que contem inicialmente 7 bolas azuis e 3 brancas, essas retiradas serão dependentes? Caso sejam, de que tipo seria essa dependência? E se as retiradas fossem simultâneas? Por mais simples que pareçam, essas questões fazem parte do alicerce da teoria de probabilidades e foi a busca por respostas a perguntas similares a estas que levaram grandes matemáticos como Thomas Bayes, Kolmogorov, Fisher, Pearson e muitos outros, a contribuírem no desvendar desse fascinante universo das incertezas. Em particular, pode-se citar Andrei Markov, precursor no estudo da propriedade da perda de memória, propriedade que levou ao desenvolvimento da teoria sobre cadeias de Markov, ferramenta de grande aplicabilidade nos mais diversos ramos da ciência. Um dos exemplos mais clássicos de aplicabilidade das cadeias ou algoritmos de Markov talvez seja em teoria dos jogos, onde pode-se provar com indiscutível simplicidade o problema da ruína do jogador. Outro ramo bastante fecundo em cadeias de Markov é a teoria de filas, a qual busca modelar matematicamente o comportamento de uma fila a fim de satisfazer da melhor forma possível o cliente, usuário da fila, e de modo que seja economicamente viável ao prestador de serviços. Na mesma linha de importância, podemos citar também a aplicabilidade dessa teoria em processos migratórios, epidemiológicos, difusão de informação e muitos outros.
O algoritimo de Markov, nomeado assim em homenagem à Andrei Markov, é um sistema de reescrita de cadeias para operar sobre cadeias de símbolos. Os algoritimos de Markov se mostraram Turing-completos sendo este um sistema de regra de manipulação de dados, o que garante que eles provêm de um modelo que podem representar qualquer expressão matemática.
O objetivo deste capitulo é a inserção no ambiente de pesquisa e a integração do aluno pesquisador de graduação que busca conhecimento nas áreas afins a probabilidade e estatística. Neste trabalho, o aluno fez estudos que envolvia os conceitos básicos de Cadeias de Markov, concentrando-se principalmente na questão de simulações de cadeias a tempo discreto. Antes desse estudo em particular, foram revisados os seguintes conteúdos: Análise combinatória, probabilidade, teoria básica de grafos, processos estocásticos. Após estudar os assuntos citados acima, foram analisados alguns exemplos clássicos de cadeias de Markov, implementou-se algoritmos com aplicações que utilizaram esses conceitos. Por fim, um modelo de disseminação de informação com características markovianas foi apresentado e implementado computacionalmente.
Uma cadeia de Markov é uma sequência de variáveis aleatórias {Xi : i = 0, 1, 2, . . .} com a propriedade de Markov que diz que dado o estado presente, os estados futuro e passado são independentes, ou seja, para todos os conjuntos mensuráveis A, P(Xt+1 ∈ A|X0 = x0, . . . , Xt = xt) = P(Xt+1 ∈ A|Xt = xt) (3.2) vale para os tempos t = 0, 1, . . . (Adrian Hinojosa Luna, 2007).
A perda de memória é a base da caracterização das cadeias de Markov e ela estabelece que em um conjunto de estados discretos o futuro só depende do estado presente, ou seja, os estados anteriores são irrelevantes para a predição dos estados seguintes, desde que o estado atual seja conhecido. Em termos de probabilidades, uma cadeia de Markov a tempo discreto com espaço de estados S é um processo estocástico {Xn}n∈T, onde T = {0, 1, 2, ...}, tal que se verificam as seguintes propriedades: 
• Para qualquer i ∈ S tem-se: P(X0 = i) = Pi . 
• Para quaisquer i, j ∈ S, e n ∈ T: P(Xn+1 = j|Xn = i) = Pij. 
• Para quaisquer n ∈ T e i0, i1, ..., in−1, i, j ∈ S, vale a condição: P(Xn+1 = j|Xn = i, Xn−1 = in−1 . . . X0 = i0) = P(Xn+1 = j|Xn = i). 
No caso Xn = i diz-se que o processo no instante n está no estado i. Em especial, a terceira propriedade nos diz que dado o presente (Xn), o futuro (Xn+1) e o passado (X0, X1, ..., Xn−1) são independentes.
4.1. Processo Estocástico no Algoritimo de Markov
A concepção de processo estocástico é uma extensão do que a probabilidade define por variável aleatória. De modo geral, uma coleção de variáveis aleatórias Xt indexadas em um conjunto de índices T, t ∈ T, frequentemente interpretado como tempo, é chamado de processo estocástico. O conjunto S no qual a variável aleatória Xt assume valores é o conjunto de estados do processo. Um exemplo de processo estocástico é dado pelo capital acumulado por uma pessoa que aposta em um jogo de cara e coroa no qual o jogador ganha Kzs 1,00 caso ocorra cara no lançamento da moeda, ou perde Kzs 1,00 se der coroa. Representando por Xt o valor recebido ou pago à banca pelo jogador na sétima jogada, com t ∈ T = {0, 1, 2, 3, . . .}, ou seja, a variável aleatória dada por: 
Os Processos Estocásticos podem ser classificados como: 
a) Em relação ao Estado 
 Estado Discreto (cadeia): X(t) é definido sobre um conjunto enumerável ou finito. 
 Estado Contínuo (sequência): X(t) caso contrário. 
b) Em relação ao Tempo (Parâmetro)
 
 Tempo Discreto: t é finito ou enumerável. 
 Tempo Contínuo: t caso contrário. 
Exemplos: 
1. Número de usuários em uma fila de banco em um determinado instante: Estado Discreto e Tempo Contínuo. 
2. Índice pluviométrico diário: Estado Contínuo e Tempo Discreto. 
3. Número de dias chuvosos: Estado Discreto e Tempo Discreto. 
Existem vários "tipos" de Processos Estocásticos, porém, nestas notas de aula será apenas abordado um tipo de Processo Estocástico denominadoProcesso Markoviano.
4.2. Processos Markovianos 
Um Processo Estocástico é dito ser um Processo Markoviano se: 
A expressão 1 pode ser traduzida por: a probabilidade condicional de qualquer evento futuro, dado qualquer evento passado e o estado presente X(tk) = xk, é independente do evento passado e depende somente do estado presente. 
Em termos mais resumidos: um Processo Estocástico é dito ser um Processo Markoviano se o estado futuro depende apenas do estado presente e não dos estados passados. 
Este tipo de processo estocástico é também denominado de Memoryless Process, ou processo sem memória, uma vez que o passado é esquecido (desprezado). 
As probabilidades condicionais são denominadas probabilidades de transição e representam, portanto, a probabilidade do estado X t( ) k+1 ser k 1 x + no instante tk+1 dado que o estado X t( ) k é k x no instante tk.
4.3. Simulação De Uma Cadeia De Markov
 
Para construir um algoritmo de simulação de uma cadeia de Markov precisamos construir duas funções: 
· Funções inicial: ψ : [0, 1] → S simula o valor inicial da cadeia com base na distribuição π 0 
· Função de atualização: φ : S × [0, 1] → S atualizarão o estado da cadeia em cada instante de tempo.
5. Gramáticas De Chomsky 
Este capitulo tem por tema central Gramaticas de Chomsky, fara-se a exposição dos principais aspectos da linguística desenvolvida pelo autor contemporâneo Noam Chomsky, assim como de suas implicações filosóficas. Isso posto, é conveniente antepor aqui algumas considerações prévias para orientar a leitura deste capitulo.
É preciso ter em mente, desde o princípio, que a obra de Chomsky é de dificílima compreensão, em virtude de três razões principais, nenhuma delas, no entanto, diz respeito à dificuldade de expressão por parte do autor. Em primeiro lugar, para compreender perfeitamente os escritos de Chomsky, o leitor precisa dominar não apenas os conceitos da linguística, mas também os conceitos de outros grandes domínios do saber, como, por exemplo, a filosofia, a teoria computacional, a lógica matemática moderna e, em domínios mais elevados, em particular, as teorias das funções recursivas. Em segundo lugar, constitui uma grande dificuldade na leitura de seus textos o fato de Chomsky estar sempre disposto a cunhar novos conceitos. Com efeito, ele introduz novos conceitos designando-os por termos criados por ele próprio, sem, contudo, proceder a uma definição explícita dos mesmos, deixando ao leitor a tarefa de retirar do contexto o significado pretendido por ele. Um exemplo disso é a expressão universais linguísticos, que, apesar de não ser explicitamente definida por Chomsky, aparece em diversos contextos designando todas as propriedades comuns às línguas naturais humanas. E, por último, constitui uma dificuldade adicional, sobretudo para quem está empenhado num trabalho de interpretação de sua obra, o fato de Chomsky ainda estar plenamente ativo em suas investigações, das quais, além disso, resultam não uma teoria em seu estágio final, mas uma teoria in statu nascendi, cuja versão definitiva ainda está longe de se delinear. 
5.1. A Revolução De Chomsky: Do Estruturalismo Ao Gerativismo
Pretende-se expor em linhas gerais o tipo de abordagem da linguagem que é característico da gramática gerativa de Chomsky, que tem sido considerada por muitos linguistas como uma das mais importantes teorias sobre a linguagem já elaborada. Com efeito, a abordagem característica da gramática gerativa é em geral seriamente levada em consideração por aqueles que se dedicam ao estudo da linguística e ao entendimento da relação entre pensamento e linguagem. Como o trabalho do autor é amplo e abrange diversas áreas do conhecimento, tais como a matemática, a filosofia, a psicologia e a própria linguística, propomo-nos expor apenas em linhas gerais como a abordagem gerativa foi desenvolvida no âmbito estrito da linguística, e, de início, nas obras Syntactic Structures (SyS) e Aspects of the Theory of Syntax (Aspects), assim como as mudanças relevantes que ela sofreu, posteriormente, nas obras mais atuais do autor. Num primeiro momento, é conveniente que comecemos por apresentar um breve relato dos pontos de convergência e divergência entre a lingüística contemporânea em comparação com a gramática tradicional, a discussão entre as supostas línguas civilizadas e as primitivas. Há estruturas comuns a todas as línguas, tais como estruturas sintáticas, combinações fonológicas e semânticas que são características comuns da linguagem humana assim como o aspecto da criatividade. Uma vez que esses aspectos polêmicos tenham sido discutidos, apresentaremos, na sequência, as duas principais abordagens que eram então majoritárias no campo da linguística, a saber, o estruturalismo e o behaviorismo, para em seguida estimar por contraste o grande desenvolvimento teórico promovido por Chomsky. 
5.2. Linguística Contemporânea e Gramática Tradicional 
A linguística contemporânea se compreende como uma ciência da linguagem, no sentido de visar a uma descrição científica de seu objeto, ou seja, de buscar investigar sistematicamente a linguagem, tendo por base observações objetivamente verificáveis dentro de um quadro categorial de uma teoria geral apropriada aos dados em questão. Assim compreendida, a linguística vem sendo desenvolvida apenas muito recentemente. No que se segue, apresentaremos algumas características dos objetivos e da atitude teórica da linguística contemporânea, em oposição aos da gramática tradicional. Em primeiro lugar, do mesmo modo que as ciências particulares, tais como a física, a biologia, a sociologia, etc., haviam se desenvolvido num processo de diferenciação e de busca de autonomia frente à filosofia e à religião, também a linguística contemporânea se constituiu buscando marcar sua diferença e autonomia frente a outras disciplinas. As disciplinas frente às quais a linguística contemporânea marca sua autonomia são, sobretudo, a filosofia e a crítica literária, no seio das quais a gramática tradicional surgira e se desenvolvera, ainda na Grécia do período clássico. Ao afirmar sua independência e autonomia, a linguística contemporânea está reivindicando o direito de abordar seu objeto de estudo de uma maneira completamente livre de compromissos com ideias tradicionais e de não ter de adotar o mesmo ponto de vista de filósofos, psicólogos, críticos literários ou representantes de outras disciplinas. Por ter se originado em conexão estreita com a crítica literária, a gramática tradicional apresentava a tendência a dar atenção exclusiva à linguagem escrita, em detrimento da linguagem falada, ignorando as especificidades de cada uma delas. A linguagem falada era geralmente deixada de lado sob a alegação de ser apenas uma cópia imperfeita da linguagem escrita. Em contraposição a isso, os linguistas contemporâneos assumem, como uma espécie de um axioma, que a linguagem escrita é secundária e derivada da linguagem falada. Ou seja, de acordo com os últimos, é nos sons, mais exatamente, no conjunto dos sons que podem ser produzidos pelos assim chamados órgãos da fala que a linguagem está incorporada.
5.3. O Estruturalismo E O Behaviorismo 
A linguística de Chomsky surgiu e se desenvolveu como uma reação contra uma determinada escola de linguistas, o estruturalismo americano, que não deve ser confundido com o estruturalismo europeu, principalmente com o estruturalismo ligado ao nome de Ferdinand de Saussure. Porém, ao desenvolver sua própria concepção sobre a linguística, Chomsky veio também a se contrapor a uma escola muito influente na psicologia, a saber, o behaviorismo, cujos pressupostos teóricos eram compartilhados por Leonard Bloomfield, um dos mais importantes representantes do estruturalismo linguístico norte-americano. Desse modo, a seguir, procederemos a uma breve exposição dos objetivos e métodos característicos do estruturalismo americano, assim como da influência que recebeu do behaviorismo, com vistas a fazer ressaltar melhor por contraste a novidade presente na proposta de Chomsky.Historicamente falando, o estruturalismo norte-americano deve sua origem às investigações acerca das línguas indígenas norte-americanas, tais como podem ser encontradas no Manual das Línguas Indígenas Americanas, publicado em 1911, cuja introdução fora escrita pelo renomado antropólogo Franz Boas. Tendo por objetivo descrever o mais exaustivamente possível a estrutura das línguas indígenas do continente americano, que já àquela época estavam em vias de extinção, tornam-se imediatamente compreensíveis o caráter eminentemente prático e o sentido de urgência desses primeiros estudos. Com efeito, havia um sentido de urgência em catalogar, descrever e analisar as línguas indígenas que estavam se perdendo. E, em conformidade com o espírito de uma linguística que se pretendia científica e autônoma, os linguistas daquela época esforçavam-se por evitar a projeção de intuições subjetivas e pessoais, suas ou dos próprios falantes, e de categorias provenientes das línguas que lhes eram conhecidas ou familiares, sobretudo as do latim e grego, no estudo de línguas exóticas como as dos indígenas. Na verdade, o estudo das últimas feito com isenção de pressupostos teria mostrado que as categorias tradicionais não estão necessariamente presentes em todas as línguas e, reciprocamente, que certas línguas fazem distinções que são desconhecidas pelas línguas tradicionais. Isso levou Boas a concluir que cada língua possuiria uma estrutura gramatical única e própria e que, por conseguinte, a tarefa do linguista consistiria justamente em descobrir as categorias descritivas apropriadas a cada língua. Assim, o estruturalismo tinha diante de si uma tarefa de cunho essencialmente descritivo, em cuja execução procurava-se evitar que houvesse interferências de conhecimentos prévios por parte do linguista. Desse modo, um princípio heurístico fundamental para o estruturalismo consistia na recomendação de que as categorias gramaticais não fossem impostas aos dados, mas, sim, por assim dizer, extraídas dos dados. Ou seja, o estruturalismo norte-americano caracteriza-se fundamentalmente pelo empirismo e pela adoção de um procedimento indutivo radical, pois, nas palavras de Bloomfield, as únicas generalizações úteis a respeito da linguagem são as de ordem indutiva. De acordo com isso, a etapa inicial da investigação linguística deveria consistir na elaboração, com base na experiência, de catálogos os mais extensos possíveis de registros linguísticos, ou seja, na elaboração de um corpus de sentenças ou de pro ferimentos da língua a ser estudada.
5.4. Chomsky em Transição 
Ao tempo em que trabalhava com Harris, Chomsky procurava utilizar os métodos convencionais da lingüística estruturalista para estudar a sintaxe, percebendo logo, porém, que esses métodos, aparentemente adequados para o estudo dos fonemas e morfemas, não funcionavam muito bem no estudo de sentenças ou frases. Com efeito, cada língua possui um número finito de fonemas e também um número finito, embora extenso, de morfemas, de modo que é plausível tentar obter uma lista de ambos. Porém, não é plausível tentar obter uma lista de frases possíveis em uma língua, pois em virtude do número potencialmente infinito de frases que podem ser produzidas, não há um limite para as possibilidades de produção de frases novas e, para cada frase dada, não importa quão longa ela seja, sempre é possível produzir uma ainda mais longa. No âmbito das pressuposições estruturalistas, não é fácil dar conta do fato de que as línguas se constituem de um número infinito de frases. A concepção geral da teoria lingüística de Chomsky, tal como apresentada em SyS, é, sob vários aspectos, praticamente a mesma defendida pelos estruturalistas, em geral, e por Zellig Harris, em particular. Porém, em SyS, já estavam implicitamente presentes críticas a esse método de análise, as quais, rapidamente, passariam a ser explícitas. É importante ressaltar que, durante esse período inicial da produção de Chomsky, não há ainda alusão alguma ao racionalismo, característica tão marcante no seu trabalho posterior, sobretudo no que diz respeito à introdução e defesa da hipótese inatista, que nos interessa particularmente nesse trabalho. Na verdade, referências feitas a filósofos empiristas, como Goodman e Quine, poderiam até sugerir que ele, no início de sua carreira, compartilhava os mesmos pontos de vista. Como quer que seja, é certo que, naquela altura do desenvolvimento de seu trabalho, Chomsky ainda estava longe de empreender uma discussão geral sobre as implicações psicológicas e filosóficas contidas em sua concepção de gramática. Ora, tendo por objetivo justamente tematizar essas implicações psicológicas e filosóficas, temos de começar por estabelecer as teses gerais constitutivas de sua concepção de gramática. Assim, no que se segue, passaremos a discutir aspectos importantes do que ficou conhecido como gramática gerativa proposta por Chomsky. Subsequentemente, discutiremos as principais mudanças que ocorreram no modelo geral da gramática gerativa entre as obras SyS e Aspects of the Theory of Syntax. 
5.5. A Primeira Gramática De Chomsky 
Em Sys, Chomsky procede, inicialmente, a uma crítica de alguns modelos de análise mais difundidos na linguística de seu tempo, no sentido de chegar a especificar aquele que satisfaria os requisitos de uma efetiva teoria sintática. De saída, empreende uma crítica a Markov, um matemático russo que pretendia criar um mecanismo capaz de produzir frases, a partir de um conjunto finito de diferentes estados internos ao próprio mecanismo, de modo que, na medida em que essa máquina fosse alternando entre um estado e outro, iria produzir um determinado símbolo ou palavra. A ideia subjacente ao projeto é a de que a máquina partiria de um estado inicial, passando por uma sequência de estados, até chegar ao estado final, no qual ela teria produzido o que chamamos de frase. Uma língua qualquer produzida por tal máquina seria chamado de língua de estado finito, e a gramática com base na qual essa língua teria sido produzida seria chamada de gramática de estado finito. As idealizadas máquinas capazes de produzir semelhantes línguas são conhecidas, matematicamente, como processos de estados finitos de Markov. Diante dessa proposta, Chomsky observa que, se pretendêssemos adotar esse modelo para explicar uma língua, poderíamos considerar um falante como sendo, essencialmente, uma máquina desse tipo. Entretanto, afirma Chomsky, as línguas naturais, tais como o inglês, português, italiano, alemão, etc. não são línguas de estado finito, sendo assim impossível construir um mecanismo, como o proposto por Markov, capaz de produzir todas as frases gramaticais do inglês, e somente elas, e, de resto, as de qualquer outra língua natural. Diante disso, Chomsky conclui que o tipo de gramática necessária para gerar todas as sequências de palavras que constituem as frases gramaticais do inglês, e somente essas, não pode ser aquela que regularia o mecanismo proposto por Markov. Desse modo, prossegue Chomsky, 
Parece bastante claro que nenhuma teoria da estrutura linguística baseada exclusivamente nos modelos de processos de Markov e em similares será capaz de explicar ou dar conta da habilidade que um falante do inglês tem de produzir e compreender novos proferimentos, no mesmo passo em que rejeita outras novas sequências como não sendo pertencentes à língua.
Uma vez rejeitada a concepção do processo de produção de linguagem proposto por Markov, Chomsky passa a considerar se o outro modelo de análise dominante na época, a saber, a análise de constituintes imediatos (IC analysis), poderia fornecer um meio eficaz de dar conta da linguagem. Em conformidade com esse modelo, Bloomfield, parte, por exemplo, da frase: Poor John ran away, para ilustrar de que modo é possível dividi-la, inicialmente, em dois constituintes imediatos, a saber, Poor John e ran away. Esses elementos constituintes são, por sua vez, analisáveis em outros constituintes mais elementares, a saber, Poor e John, ran e away. Essa análise procuraevidenciar que, diferentemente do modelo proposto por Markov, a frase em questão não se constitui como uma mera sequência ou string dos elementos sucessivos Poor + John + ran + away. Trata-se antes de uma estrutura baseada em camadas, em layers de constituintes, e é por essa razão que não podemos seccionar arbitrariamente os elementos da frase, dividindo-a, por exemplo, em poor + John ran + away. Podemos ilustrar a divisão correta mediante o diagrama abaixo.
Figura 1
Fonte: Candice Helen Glenday, Lingüística E Filosofia.Pag.31
O diagrama ilustra onde é possível inserir cada ponto de corte, ou seja, cada ‘node’, e este último, por sua vez, recebe um rótulo ou label de identificação correspondente, tornando a análise mais clara e fácil de ser visualizada. 
Apesar desse modelo de análise apresentar vantagens consideráveis em comparação com o anterior, Chomsky chega à conclusão de que a análise dos constituintes imediatos também é totalmente inadequada. Segundo Chomsky, uma genuína teoria da linguagem humana tem de satisfazer a duas condições: de um lado, a condição da adequação descritiva, de outro lado, a condição da adequação explanatória. A condição de adequação descritiva vigora para a gramática de uma língua em particular; a gramática satisfaz a essa condição na medida em que dá uma explicação completa e exata das propriedades da língua, daquilo que o falante da língua sabe. Sendo assim, podemos então dizer que há dois modos de justificar a gramática gerativa. Em um nível, no da adequação descritiva, a gramática é justificada na medida em que ela descreve corretamente o seu objeto, a saber, a intuição linguística – a competência tácita – do falante nativo. Nesses termos, a gramática é justificada em termos externos, na medida em que corresponde aos fatos linguísticos. Mas, em um nível mais profundo, e muito mais complexo, temos o nível da adequação explanatória. Nesse nível, a gramática é justificada na medida em que se apresenta como um sistema descritivamente adequado aos dados linguísticos primários, com os quais é compatível. Nesse sentido, a gramática é internamente justificada em sua relação com a teoria linguística, da qual constitui uma hipótese explanatória sobre a forma da linguagem como tal. Como afirma Chomsky, em Aspects: 
Existem dois sentidos em que é possível falar de justificar uma gramática. Num nível o da adequação descritiva, a gramática é justificada na medida em que descreve corretamente seu objeto, isto é, a intuição linguística, a competência tácita, do falante nativo. Nesse sentido, a gramática é justificada por razões externas, de correspondência com o fato linguístico. Num nível muito mais profundo e, portanto, mais raramente atingível o da adequação explanatória uma gramática é justificada na medida em que constitui um sistema normativo descritivamente adequado, pelo fato de que a teoria linguística com a qual se acha associado selecionar esta gramática dentre outras, colocados certos dados linguísticos iniciais com os quais todas as gramáticas possíveis são compatíveis. Neste sentido, acha-se a gramática justificada por razões internas, por sua relação para com uma teoria linguística que constitui uma hipótese explanatória acerca da forma da linguagem enquanto tal. O problema da justificação interna ou adequação explanatória é essencialmente o problema de construir uma teoria da aquisição da linguagem, uma análise das habilidades inatas específicas que torna tal proeza possível.
6. Conclusão
Em virtudes dos fundamentos aqui apresentamos concluímos que, os temas aqui apresentados nos auxiliam a compreender melhor o funcionamento das linguagens computacionais, pois a todas elas centram-se nos conceitos da teoria computacional. Assim como os seres humanos desenvolveram uma linguagem humana para a comunicação entre a raça humana, graças a muitos estudiosos antigos da tecnologia, hoje também temos linguagens computacionais que permitem a comunicação entre a máquina e o ser humano através das instruções a eles submetidas que são interpretadas e compiladas para a sua devida execução.
7. Referência Bibliográficas
Teoria das Linguagens Formais e Autómatos:
Linguagens Formais e Autômatos, Marcus Vinícius Midena Ramos, São Paulo, 2008
WWW. Wikipedia.com
Marcus Vinícius Midena Ramos, 2008
Teoria da Computação:
Revista de Computação e Tecnologia da PUC-SP — Departamento de Computação/FCET/PUC-SP ISSN 2176-7998 Vol. I No. 1
Algoritmos de Markov:
Hinojosa Luna , Introdução aos Métodos de Monte Carlo Avançados, 2010
Advanced Markov chain Monte Carlo methods, Faming Liang Chuanhai Liu e Raymond Carroll (2010).
Marcia D’Elia Branco, Analise de dados e Simulação, 2010.
Gramáticas De Chomsky
Noam Chomsky, linguística e filosofia, Campos dos Goytacazes, RJ, 2008.
Candice Helen Glenday, Lingüística E Filosofia, Campos Dos Goytacazes, 2008.