- 集合論に基づいた言語を作りたい
83 ：1[sage]：2014/08/16(土) 08:32:34.29 ID:ceF43G6L - >>81
とりあえず、正規表現と有限オートマトン、文脈自由言語とプッシュダウンオートマトン
あたりを美しく、または教科書のとおりに書きたいなと思ってる。
具体的な案はまだない。
| - 集合論に基づいた言語を作りたい
87 ：１[sage]：2014/08/16(土) 09:37:02.60 ID:ceF43G6L - だから具体的な案はまだないんだって。
| - 集合論に基づいた言語を作りたい
88 ：１[sage]：2014/08/16(土) 10:17:23.81 ID:ceF43G6L - 有限オートマトンの遷移関数を書くのに、関数の引数のパターンマッチは欲しいかな。
| - 集合論に基づいた言語を作りたい
89 ：１[sage]：2014/08/16(土) 10:35:06.72 ID:ceF43G6L - と、おもったけどそんなめんどくさいことしなくても連想配列でもいいのか。
| - 集合論に基づいた言語を作りたい
91 ：1[sage]：2014/08/16(土) 11:51:35.82 ID:ceF43G6L - 俺が持ってる教科書、マイケルシプサの計算理論の基礎っていう本の38,39ページに載ってる
A={w|wは少なくとも一つの1を含み最後に現れる1の後に偶数個の0が存在する}
っていう言語を受理するオートマトンの実装例は以下のような感じかな。かなりC++ぽいが。
enum State {q1,q2,q3};
set<State> Q={q1,q2,q3};
set<char> Σ={'0','1'};
map<pair<State,char>,State> δ={
(q1,'0')=>q1,
(q1,'1')=>q2,
(q2,'0')=>q3,
(q2,'1')=>q2,
(q3,'0')=>q2,
(q3,'1')=>q2
};
set<State> F={q2};
class Automaton {
set<State> Q;
set<char> Σ;
map<pair<State,char>,State> δ;
State start;
set<State> F;
bool accept(char *str){
State state=start;
while(str){
state=δ[(state,*str)];
str++;
}
return F.include(state);
}
} M = (Q,Σ,δ,q1,F);
| - 集合論に基づいた言語を作りたい
92 ：1[sage]：2014/08/16(土) 11:54:15.04 ID:ceF43G6L - あれ、空白ミスってんな。
プレビューでみたらちゃんと空白になってたと思ったけど。
| - 集合論に基づいた言語を作りたい
93 ：1[sage]：2014/08/16(土) 11:57:01.89 ID:ceF43G6L - まあ、いいや。インデントなしで再投稿
enum State {q1,q2,q3};
set<State> Q={q1,q2,q3};
set<char> Σ={'0','1'};
map<pair<State,char>,State> δ={
(q1,'0')=>q1,
(q1,'1')=>q2,
(q2,'0')=>q3,
(q2,'1')=>q2,
(q3,'0')=>q2,
(q3,'1')=>q2
};
set<State> F={q2};
class Automaton {
set<State> Q;
set<char> Σ;
map<pair<State,char>,State> δ;
State start;
set<State> F;
bool accept(char *str){
State state=start;
while(str){
state=δ[(state,*str)];
str++;
}
return F.include(state);
}
} M = (Q,Σ,δ,q1,F);
| - 集合論に基づいた言語を作りたい
95 ：1[sage]：2014/08/16(土) 15:25:06.91 ID:ceF43G6L - とりあえず、集合と連想配列と組のリテラル表記は欲しいな。
型さえ一致してれば組はクラスに暗黙のキャストできる感じで。
| - 集合論に基づいた言語を作りたい
97 ：１[sage]：2014/08/16(土) 17:44:24.71 ID:ceF43G6L - まじかｗ
言語仕様きめるだけでも結構大変だぞｗ
さくっと作れるみたいなこと言うなｗ
| - 集合論に基づいた言語を作りたい
99 ：１[sage]：2014/08/16(土) 17:56:17.24 ID:ceF43G6L - いまのところシンタックスシュガーの問題の域をでてないな。
オートマトンだけじゃなくてもっと色んな問題を考察していけば
なんか出てくるのかもしれないが。
とにかく、今のプログラミング言語において集合は不当に冷遇されてる気がする。
もっと集合を活躍させるべき、というのがこのスレの発端です。
| - 集合論に基づいた言語を作りたい
101 ：１[sage]：2014/08/16(土) 18:04:10.41 ID:ceF43G6L - 型のキャストって結構不自由じゃない？
集合論に基づいた型の表記法が一致したらバンバンキャストできるようにしちゃうとか。
| - 集合論に基づいた言語を作りたい
102 ：デフォルトの名無しさん[sage]：2014/08/16(土) 18:09:17.80 ID:ceF43G6L - >>100
いや、>>75を具体的に語ったのが>>93なんだけども。
残念ながら教科書コピペとはほど遠いC++チックなコードになっちゃったけど
教科書の定義にはなるべく従ったコードにしたつもり。
|
|