１２月１９日
モデル
例
文字列マッチングをする．
状態遷移図G１
入力
文字列 ω
出力
ωに“SAKURA”が入っていたら“hit”を出力
入っていなければ“not found”を出力
モデル
状態遷移図
G1
動作
初期化：状態を初期状態にする
遷移：
ωから１文字読み状態遷移図に従い、次の状態に遷移する．
終了：
ω上の文字を読み終わった時、状態ｑ６ ⇒“hit”を出力
それ以外の状態 ⇒“not found”を出力
例
G1の動作例
入力：ω＝“NUSAKURA”
状態遷移
流れ図
#include<stdio.h>
int main(void){
int state = 0;
char string[100];
char symble;
int i;
scanf("%s", string);
for(i=0; string[i]!='\0';i++){
symble = string[i];
if(state==0){
if(symble=='S'){
state = 1;
}
}else if(state==1){
if(symble=='A'){
state = 2;
}else{
state = 0;
}
}else if(state==2){
if(symble=='K'){
state = 3;
}else{
state = 0;
}
}else if(state==3){
if(symble=='U'){
state = 4;
}else{
state = 0;
}
}else if(state==4){
if(symble=='R'){
state = 5;
}else{
state = 0;
}
}else if(state==5){
if(symble=='A'){
state = 6;
}else{
state = 0;
}
}else if(state==6){
state = 6;
}
}
if(state==6){
printf("hit!");
}else{
printf("not found");
}
}
例題
課題
テーマ：状態遷移図と文字列マッチング
（問題１）各自の苗字を検索する状態遷移図Gを書け
（問題２）次のプログラムを作れ
入力 文字列 ω
出力 ωに苗字が入っている⇒“hit”
入っていない⇒“not found”
提出物
仕様書、ソース、実行例
締め切り