¿Cuántos identificadores diferentes puede tener un lenguaje de programación ficticio?

Question

¿Cuántos identificadores diferentes puede tener un lenguaje de programación ficticio, cuando deben respetarse las siguientes reglas?

1. Sólo se admiten mayúsculas, por lo que los elementos de $\{A, ..., Z\}$ ,
2. El identificador debe tener una longitud mínima de $1$ y como máximo $5$ .
3. Las palabras clave AND, OR, IF, THEN y GOTO no pueden aparecer de ninguna forma en el identificador.

Para ello, he examinado las longitudes permitidas individualmente y luego he sumado todas las combinaciones.

Longitud = 1: Aquí sólo tenemos $26$ posibilidades.

Longitud = 2: Esta vez tenemos $26^2 - 2$ ya que IF y OR no pueden aparecer.

Longitud = 3: Esta también es bastante sencilla. Tenemos $25^3 - 1 - 2*26 - 2*26$ ya que no se permite que aparezca AND y todas las combinaciones que contengan IF (IF. y .IF) u OR (OR. y .OR) no son válidas.

Longitud = 4: Aquí es donde empiezo a tener mis problemas. He intentado hacer lo mismo aquí, pero no estoy muy seguro. Hay $26^4$ combinaciones totales. Esta vez THEN y GOTO no pueden aparecer, así que $-2$ para acomodar esto. Y tampoco puede aparecer, así que $-2*26$ . Pero para IF y OR no estoy seguro de cómo calcularlo. Al principio pensé que sería simplemente $-3*26^2 - 3*26^2$ (IF. , .IF. , ..IF , OR. , .OR. , ..OR), pero entonces pensé que esto contaría ciertas combinaciones más de una vez. La combinación IFOR, por ejemplo, se contaría dos veces, así que tendría que añadir $1$ para compensarlo. Luego están las combinaciones IFIF y OROR, que también se restarían dos veces por lo que tendría que sumar $+1+1$ otra vez. Y no estoy seguro de si me perdí algunos de estos.

Así que para Longitud > 3 no sé muy bien cómo abordar esto, para que no se me escape ninguna combinación y todo el mundo se cuente una sola vez.

Answer 1

Para $n=4$ también hay que volver a añadir IFOR y ORIF . En otras palabras, todos los códigos doblemente sustraídos tienen el aspecto siguiente $$ AABB, $$ donde $AA$ y $BB$ son ambas malas palabras de longitud $2$ . Hay dos opciones para $AA$ y dos opciones para $BB$ por lo que hay que volver a añadir $2\times 2$ .

En $n=5$ hay más posibilidades para las palabras doblemente sustraídas: pueden ser $$ AABB*,\quad AA{*}BB,\quad*AABB,\\ AACCC,\quad CCCAA $$ Otra vez, $AA$ y $BB$ son palabras malsonantes arbitrarias de dos letras, y $CCC$ es una mala palabra arbitraria de tres letras (vale, sólo hay una posibilidad para $CCC$ pero intento mostrar cómo se generalizará).

Ésas parecen ser todas las formas de meter dos palabras malsonantes en una cadena de cinco letras. Pero estas son solo las formas en las que las dos palabras no se solapan. Dado que el final de GOTO coincide con el inicio de OR hay una última palabra doblemente sustraída, a saber, $$ GOTOR. $$ Puede comprobar que ésta es la única posibilidad de solapamiento. En general, si tuviera muchas posibilidades de solapamiento, las cosas serían más complicadas. Además, si $n\ge 6$ tendría que preocuparse por las palabras con tres restas, como IFOROR . Sin embargo, este problema es bastante manejable.

En resumen, inicialmente se restan las palabras que contienen cada posible mala palabra en cada posible posición, sin preocuparse por la doble contabilidad, lo que da como resultado $$26^5-4\cdot 26^3-4\cdot 26^3-3\cdot 26^2-2\cdot 26-2\cdot 26.$$ Pero entonces debes añadir todas las palabras doblemente sustraídas en los párrafos anteriores. Por ejemplo, para palabras como $AABB*$ volvería a añadir $2\times 2\times 26$ . Te veré si puedo terminar el resto.

Este tipo de recuento se denomina principio de inclusión y exclusión, o método de entrada y salida.