# Formatos de los archivos de máquinas

Los autómatas, las gramáticas y las máquinas de Turing del curso se escriben en archivos de
texto. Los ejemplos de los apuntes y los casos de los laboratorios usan estos mismos formatos
todo el semestre: el simulador que escriban una semana sirve para probar sus máquinas en las
siguientes.

## Reglas comunes

- Una línea que empieza con `#` es un comentario. Las líneas vacías del encabezado se ignoran.
- Cada campo va en una línea, con su nombre, dos puntos y los valores separados por espacios.
  Los campos van siempre en el orden que se muestra.
- El nombre de un estado o de una variable es una palabra sin espacios: `q0`, `par`, `S`.
- Un símbolo del alfabeto es **un solo carácter** visible, distinto de `#`: `0`, `a`, `(`.
- La cadena vacía se escribe `eps` donde hace falta nombrarla.
- Después de `delta:` o de `rules:` va una transición o una regla por línea, hasta el final
  de la descripción.
- Los comentarios pueden ir en cualquier línea de la descripción. Después de `delta:` o de
  `rules:` no hay líneas vacías: la descripción termina donde empieza `strings:` o donde
  termina el archivo.
- Un nombre no empieza con `#` ni termina con `:`.

Los campos se llaman igual que los componentes de la definición formal y que los miembros de
los `struct` del código: `states`, `alphabet`, `delta`, `start`, `accept`.

## DFA (`.dfa`), desde la semana 1

```text
# Cadenas binarias con una cantidad par de unos.
states: par impar
alphabet: 0 1
start: par
accept: par
delta:
par 0 par
par 1 impar
impar 0 impar
impar 1 par
```

- `accept:` puede quedar vacío: el autómata no acepta nada.
- En `delta:`, cada línea es `estado símbolo destino`. Debe haber exactamente una línea por
  cada par de estado y símbolo, porque en un DFA la función de transición es total.

## NFA (`.nfa`), desde la semana 2

```text
# El tercer símbolo desde el final es 1.
states: q0 q1 q2 q3
alphabet: 0 1
start: q0
accept: q3
delta:
q0 0 q0
q0 1 q0 q1
q1 0 q2
q1 1 q2
q2 0 q3
q2 1 q3
```

- Cada línea es `estado símbolo destino…`, con uno o más destinos.
- Una transición ε usa `eps` en lugar del símbolo: `q0 eps q1 q2`.
- Un par de estado y símbolo sin línea no tiene transiciones: ese camino muere.
- El mismo par de estado y símbolo puede aparecer en varias líneas: sus destinos se juntan.
- Todo archivo `.dfa` es también un `.nfa` válido.

## Gramática libre de contexto (`.cfg`), desde la semana 5

```text
# Paréntesis balanceados.
variables: S
terminals: ( )
start: S
rules:
S -> ( S ) S | eps
```

- Cada línea es `variable -> alternativa | alternativa…`. Los símbolos de una alternativa
  van separados por espacios.
- Una alternativa vacía se escribe `eps`.
- Una variable puede tener varias líneas: sus alternativas se juntan.
- Ni `|` ni `eps` pueden ser el nombre de una variable o de un terminal, y ningún nombre es
  a la vez variable y terminal.

## Autómata de pila (`.pda`), desde la semana 6

```text
# { 0^n 1^n : n >= 0 }
states: q0 q1 q2 q3
alphabet: 0 1
stack: 0 $
start: q0
accept: q0 q3
delta:
q0 eps eps -> q1 $
q1 0 eps -> q1 0
q1 1 0 -> q2 eps
q2 1 0 -> q2 eps
q2 eps $ -> q3 eps
```

- `stack:` es el alfabeto de la pila. Cada símbolo es un solo carácter, como los del alfabeto de
  entrada, y el campo puede quedar vacío.
- Cada línea es `estado lee saca -> destino pone`. Cualquiera de `lee`, `saca` y `pone`
  puede ser `eps`.
- Puede haber varias líneas con el mismo lado izquierdo: el autómata es no determinista.
- Acepta si, al terminar de leer la entrada, algún camino está en un estado de aceptación.

## Máquina de Turing (`.tm`), desde la semana 7

```text
# Decide { 0^n 1^n : n >= 0 }.
states: q0 q1 q2 q3 q_accept q_reject
alphabet: 0 1
tape: 0 1 X Y _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q1 X R
q0 Y -> q3 Y R
q0 _ -> q_accept _ R
q1 0 -> q1 0 R
q1 Y -> q1 Y R
q1 1 -> q2 Y L
q2 0 -> q2 0 L
q2 Y -> q2 Y L
q2 X -> q0 X R
q3 Y -> q3 Y R
q3 _ -> q_accept _ R
```

- `alphabet:` es el alfabeto de entrada y `tape:` el de la cinta, que lo contiene. El símbolo
  blanco es `_`.
- Cada línea es `estado lee -> destino escribe movimiento`, con movimiento `L` o `R`.
- Un par de estado y símbolo sin línea lleva a `reject`.
- La cinta es infinita solo hacia la derecha. Un movimiento `L` en la primera celda deja el
  cabezal donde está, como en Sipser.
- Una máquina **no determinista** se escribe igual, con varias líneas para el
  mismo par de estado y símbolo.

## Cadenas de entrada

Cuando un programa de laboratorio recibe una máquina y varias cadenas, las cadenas van
después de la descripción, así:

```text
strings: 3
0110

111
```

- `strings:` dice cuántas cadenas siguen, una por línea.
- Una línea vacía es la cadena vacía ε: en el ejemplo, la segunda cadena.
- Las cadenas solo usan símbolos del alfabeto de la máquina.
- Lean las cadenas con `std::getline`, no con `>>`, que se salta las líneas vacías.
