La idea básica es considerar a un lenguaje como un conjunto compuesto por cadenas de longitud finita formadas por símbolos tomados de un alfabeto. Es decir, dado un alfabeto , decimos que , (para un dado, que llamamos longitud de ) es una cadena construida con símbolos de . Si tenemos la cadena llamada vacia, y denotada por . Al conjunto formado por de todas las cadenas que se pueden construir con las letras de dicho alfabeto se le llama lenguaje universal y se le denota por * . Es evidente que el número de elementos de * es infinito numerable. Entre las cadenas, como elementos de * , se define una operación, llamada concatenación, mediante la cual a dos cadenas dadas * se le asocia otra cadena obtenida por yuxtaposición de ; es decir, si *, e *, entonces la cadena , sería : .
Llamamos lenguaje construido con el alfabeto , a cualquier subconjunto L de *. Diremos que un lenguaje es finito, si es finito el número de cadenas de que consta; en otro caso diremos que es infinito. El lenguaje vacio no tiene ninguna cadena (que no debe confundirse con el lenguaje que solo tiene la cadena vacia).
Una vez dada esta definición tan general de lenguaje, el problema inicial que se nos presenta es como distinguir con precisión las cadenas que pertenecen a un lenguaje L de aquellas que no pertenecen. Hay dos formas de hacerlo: una consiste en dar las reglas mediante las cuales construir las cadenas que forman el lenguaje, y otra es dar un procedimiento para determinar si una cadena dada pertenece o no al lenguaje considerado. En el primer caso se trata de definir las gramáticas formales, o generadores, y en el otro los autómatas o reconocedores.
Para fijar un poco las ideas de lo que se entiende por lenguaje definido por una gramática formal, demos ligeramente algunos detalles técnicos. Una gramática es un procedimiento finito para formar o generar cualquiera de todas las posibles cadenas de un lenguaje. Formalmente diremos que una gramática es un sistema :
Donde es un alfabeto llamado vocabulario no terminal; es un alfabeto, llamado vocabulario terminal. Las reglas de son de la forma
, donde
A la derivación , se la puede expresar:
o simplemente
que podría leerse: se obtiene por derivación de aplicando reglas de , o simplemente: en una derivada de .
Podemos sintetizar lo anterior diciendo que el lenguaje generado por la gramática , es: