Teoría de lenguajes formales
El text desenvolupa una breu introducció a la teoria dels llenguatges formals i a la teoria de la complexitat computacionals orientada a l'aplicació d'aquestes teories en l'àmbit de la recerca en lingüística i en ciència cognitiva. Després d'una introducció on es presenten algunes nocions matemàtiqu...
| Author: | |
|---|---|
| Format: | Book |
| Publication date: | 2014 |
| Country: | España |
| Institution: | Universitat Autònoma de Barcelona |
| Repository: | Dipòsit Digital de Documents de la UAB |
| Language: | Spanish |
| OAI Identifier: | oai:ddd.uab.cat:116304 |
| Online Access: | https://ddd.uab.cat/record/116304 |
| Access Level: | Open access |
| Keyword: | Llenguatges formals Autòmats Complexitat computacional Lingüística Formal languages Automata Computational complexity Linguistics |
| Summary: | El text desenvolupa una breu introducció a la teoria dels llenguatges formals i a la teoria de la complexitat computacionals orientada a l'aplicació d'aquestes teories en l'àmbit de la recerca en lingüística i en ciència cognitiva. Després d'una introducció on es presenten algunes nocions matemàtiques bàsiques, el treball s'ocupa amb detall dels sistemes regulars i els sistemes independents del context per, més endavant, tractar aquells sistemes avui en dia classificats com a moderadament sensibles al context, amb especial atenció als "Linear Context-Free Rewriting Systems". La part final, s'ocupa de computabilitat i màquines de Turing per tal d'introduir al lector en el concepte de classe de complexitat computacional de TEMPS i d'ESPAI. Aquesta part es tanca amb algunes consideracions sobre la conjectura si les classes P i NP són iguals o no. |
|---|