C言語でL21有限オートマトンのプログラム

Question

C言語でL21有限オートマトンのプログラムを作りたいのですが、どこを直せばうまく機能してくれるのでしょうか？
aのm乗bのｎ乗｜m,n>0が成り立つプログラムを作りたいです。
例えばaaabだとしたらＹＥＳと表示され、
bbaとかだとＮＯと表示されるプログラムです。

#define p 0
#define q 1
#define r 2
#define d 3
#include <stdio.h>
int main(void)
{
	int s;
	char c[30];
	s=p;
	scanf("%s",c);
	while( c!='\0' ){
		if(( s==p ) && (s=='a')){
			s=q;
		} else if(( s==p ) && ( c='b' )){
			s=d;
		} else if(( s==q ) && ( c='a' )){
			s=q;
		} else if(( s==q ) && ( c='b' )){
			s=r;
		} else if(( s==r ) && ( c='a' )){
			s=d;
		} else if(( s==r ) && ( c='b' )){
			s=r;
		} else if(( s==d ) && ( c='a' )){
			s=d;	
		} else if(( s==d ) && ( c='b' )){
			s=d;
		}
	}
	if( s==r ){
		printf("Yes");
	} else{
		printf("No");
	}
}

Comments

[y_waiwai]

提示のコードではどういう不具合があるんでしょうか

[kazuma-s]

質問では「m,n>0が成り立つ」となっていますが、
「m - n > 0」または「m > n」の間違いではありませんか？

[yukihirotahu]

m、n>0が成り立つで合っています。
最初が必ずaから始まってbで終わらなければいけなく、aが1でbが2だったらabbです。

[kazuma-s]

「m,n>0」と書かれたら「m>0 かつ n>0」と普通は解釈しませんか？
それなら、m=1 かつ n=2 でどちらも正なので YES になってしまいます。
「m > n > 0」の間違いではありませんか？

aabb は YES ですか、NO ですか？

それから、「L21有限オートマトン」とはなんですか？
普通の有限オートマトンなら分かるんですが、L21 が何を意味しているのかが分かりません。

さらに、aがm個と b がn個で m > n ということは、受理できる文字列は次の BNF で表せるのはないでしょうか？
非終端記号を {S, T, U}、終端記号を {a, b}、開始記号を S とし、
S := T U
T := a | a T
U := a b | a U b
するとこれは文脈自由文法であり、プッシュダウンオートマトンなのではありませんか？
有限オートマトンではないように思います。

Answer 1

質問のコードは変数の型と値が完全におかしいのでダメです。

次のように書けば、入力文字列を受理できるかどうか判定できると思います。

#include <stdio.h>

int automaton(const char *s)
{
	int m = 0, n = 0, i = 0;
	for (; s[i] == 'a'; i++) m++;
	for (; s[i] == 'b'; i++) n++;
	return s[i] == '\0' && m > n && n > 0;
}

int main(void)
{
    char s[100];
	while (printf(">> "), scanf("%99s", s) == 1)
		puts(automaton(s) ? "YES" : "NO");
}

実行例

$ ./a.out
>> a
NO
>> b
NO
>> aa
NO
>> ab
NO
>> ba
NO
>> bb
NO
>> aaa
NO
>> aab
YES
>> abb
NO
>> aba
NO
>> baa
NO
>> aaab
YES
>> ^D
$ 

追記
状態変数 s と状態 { p, q, d } で有限オートマトン風に書き直してみました。

#include <stdio.h>

enum { p = 0, q = 1, d = -1 };

int automaton(const char *str)
{
	int s = p, c;
	while (s != d && (c = *str++))
		if (s == p && c == 'a') s = q;
		else if (s == p && c == 'b') s = d;
		else if (s == q && c == 'a') s++;
		else if (s == q && c == 'b') s = d;
		else if (s >  q && c == 'a') s++;
		else if (s >  q && c == 'b') s = -s;
		else if (s <  d && c == 'a') s = d;
		else if (s <  d && c == 'b') s++;
	return s < d;
}

int main(void)
{
    char s[100];
	while (printf(">> "), scanf("%99s", s) == 1)
		puts(automaton(s) ? "YES" : "NO");
}

しかし、状態は { p, q, d, >q, <d } であり、
q より大きい数は無数にあるので、 これを有限状態とは言えません。

追記2

例えばaaabだとしたらＹＥＳと表示され、

bbaとかだとＮＯと表示されるプログラムです。

私はこれを読み違えて、aaab は YES、abb は NO と書かれているものだと
信じ込んでいました。
だから、m > n という条件を勝手に想定していました。
そして、それは有限オートマトンにはなりえないと言ってしまいました。

m > 0 かつ n > 0 という条件があるだけで m と n の大小が無関係なら
それは "a+b+" または "aabb" という正規表現で表せるので、
4つの状態を持つ有限オートマトンになります。

質問のコードを修正するとすれば、

#include <stdio.h>

#define p 0
#define q 1
#define r 2
#define d 3

int main(void)
{
    int s = p, c;
    char str[30];
    scanf("%s", str);
    for (int i = 0; c = str[i]; i++) {
        if (s == p && c == 'a') s = q;
        else if (s == p && c == 'b') s = d;
        else if (s == q && c == 'a') s = q;
        else if (s == q && c == 'b') s = r;
        else if (s == r && c == 'a') s = d;
        else if (s == r && c == 'b') s = r;
        else if (s == d && c == 'a') s = d;
        else if (s == d && c == 'b') s = d;
    }
    if (s == r)
        puts("Yes");
    else
        puts("No");
}

Answer 2

cが¥0になるまで続けるときどのように条件分式を書けばいいのでしょうか？
==にしても=にしてもエラーが出てしまいます。

Comments

[kazuma-s]

char c[30]; と宣言されているので、c の型は配列です。
これを c[i] という形ではなく、c で参照すると、c はポインタ型の値に変換され、その値は c[0] のアドレスです。c[0] のアドレスは固定されているので、その値が '\0' になることはありません。
配列 c の中の文字列を 1文字ずつ参照するのは、c[i] です。i を 1つずつ増やすことによって、
全部の文字を参照でき、c[i] == '\0' となったときがループの終了です。

Answer 3

まず、

while( c!='\0' ){

これおかしいですね
cは配列です

} else if(( s==p ) && ( c='b' )){

cに代入になってますが、
cは配列です

Comments

[yukihirotahu]

cが¥0になるまで続けるときどのように条件分式を書けばいいのでしょうか？
==にしても=にしてもエラーが出てしまいます。