## Exercise 1

One possible solution is: (a+b)*bba*.

## Exercise 3

We construct the NFA directly (not from the previous NFA-lambda)

## Exercise 5

We give the solution in C.
```#include <stdio.h>
#include <string.h>

int main() {
char crt_symb; /* The current input symbol */
int crt_state; /* The current state. The states will be represented by 0,1,2,3 */
int delta[4][2] = {{0,1},
{0,2},
{3,2},
{3,1}}; /* The transition relation. The rows represent the
states, the colums represent the input symbols
a and b respectively */
int col; /* Integer which will represent the column associated to a (0) and b (1) */

crt_state = 0; /* The initial state is 0 */
printf("Enter the input string on the alphabet {a,b} \n(type c to mark the end of the input): ");
scanf("%c", &crt_symb);

while (crt_symb != 'c') {
if (crt_symb == 'a')
col = 0;
else
col = 1;
crt_state = delta[crt_state][col];
scanf("%c", &crt_symb);
}

if (crt_state == 2 || crt_state == 3)
printf("Input string accepted \n");
else
printf("Input string rejected \n");
}
```