# Implement an FSM that can recognize a simple patterns of strings

Page 1 of 1

## 3 Replies - 854 Views - Last Post: 02 November 2015 - 11:14 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=383939&amp;s=e46630904d42b26d936ee0180366a472&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 westin467

• New D.I.C Head

Reputation: 0
• Posts: 20
• Joined: 27-September 15

# Implement an FSM that can recognize a simple patterns of strings

Posted 02 November 2015 - 01:34 PM

Problem) Your task is to implement an FSM that can recognize a simple patterns of strings such as:
ha!
haha! hahaha!
ho!
hoho! hohoho! hahohoho! hahohahoha!

Basically, the pattern to be recognized is a sequence of “ha” or “ho”, or a mixture of both. The sequence can be of any length (at least greater than three, i.e., the shortest sequence is “ha!” or “ho!”). There is no restriction on how many “ha”s or “ho”s the sequence can contain, and the “ha”s and “ho”s can appear in any order if the sequence is a mixture of both. The string must end with one “!”.

Implement the above FSM to recognize whether a given string conforms to the specific pattern or not. Keep prompting the user for typing in a string, scan through the user’s input string and transit the FSM accordingly. Report to the user whether the input string conforms to the FSM pattern or not.

Quit the program when the user types in “bye”.

----------------------------------------------------------------------------------------------

What I tried:
[
```#include <stdio.h>
#include <string.h>
int main(int argc, char** argv) {

// The user's input string will be stored in this char array
char buffer[99];

while(1) {
printf("I can recognize if you are laughing or not, please type in a string:\n");
scanf("%s", buffer);
printf("\n");

// strcmp is a function that compares whether two strings are equal or not
if(strcmp(buffer, "bye") == 0) {
printf("Bye now!\n");
break;
}

printf("Your input is: %s\n", buffer);

// strlen is a function that returns the length of a string
int len = strlen(buffer);
printf("You just typed: %s\n", buffer);
printf("It is %d characters long\n", len);

// Scan through the string character-by-character using a for loop
printf("Now scanning through the string character-by-character:\n");
int i;
for(i = 0; i < len; i++) {
printf("Character %d is %c\n", i + 1, buffer[i]);
}

printf("\n");
}

return (EXIT_SUCCESS);
}
```

]

ps: I am not sure how to tag my code, I'm using brackets but apparently I'm still doing it wrong

This post has been edited by modi123_1: 02 November 2015 - 01:37 PM
Reason for edit:: In the future - please use the 'code' tag button in the editor for readability.

Is This A Good Question/Topic? 0

## Replies To: Implement an FSM that can recognize a simple patterns of strings

### #2 modi123_1

• Suitor #2

Reputation: 13954
• Posts: 55,694
• Joined: 12-June 08

## Re: Implement an FSM that can recognize a simple patterns of strings

Posted 02 November 2015 - 01:38 PM

What's the question?

### #3 westin467

• New D.I.C Head

Reputation: 0
• Posts: 20
• Joined: 27-September 15

## Re: Implement an FSM that can recognize a simple patterns of strings

Posted 02 November 2015 - 02:30 PM

I am confused to how to get a an output like this sample output.

Sample Output
<arctic:~ >a.out
I can recognize if you are laughing or not, please type in a string: ha! Your input is: ha!
You are laughing!
I can recognize if you are laughing or not, please type in a string: haha! Your input is: haha!
You are laughing!
I can recognize if you are laughing or not, please type in a string: ho! Your input is: ho!
You are laughing!
I can recognize if you are laughing or not, please type in a string: hohohaha! Your input is: hohohaha!
You are laughing!
I can recognize if you are laughing or not, please type in a string: haa! Your input is: haa!
You are not laughing...
I can recognize if you are laughing or not, please type in a string: ha!! Your input is: ha!!
You are not laughing...
I can recognize if you are laughing or not, please type in a string: ha!ha Your input is: ha!ha
You are not laughing...
I can recognize if you are laughing or not, please type in a string: bye Bye now!

### #4 Salem_c

• void main'ers are DOOMED

Reputation: 2140
• Posts: 4,206
• Joined: 30-May 10

## Re: Implement an FSM that can recognize a simple patterns of strings

Posted 02 November 2015 - 11:14 PM

https://en.wikipedia...e-state_machine
Now draw a diagram of your recogniser.

A simple idea for implementing an FSM
```enum States {
Initial,
Found_h,
Found_o,
Found_ex,
};

enum States state = Initial;
while ( (ch=buffer[i++]) != 0 ) {
switch ( state ) {
case Initial:
if ( ch == 'h' ) {
state = Found_h;
} else {
state = Initial;
}
}
}

```