解答集

目次

• 第1回
• 第2回
• 第3回
• 第4回
• 第5回
• 第6回
• 第7回
• 第8回
• 第9回
• 第10回
• 第11回
• 第12回

第1回

演習1-1

略

演習1-2

略

演習1-3

/* testf.c */
#include <stdio.h>
int combination(int n,int m);
int main(void){
  int in1[]={0,1,1,5,-1};
  int in2[]={0,0,1,2,-1};
  int out[]={1,1,1,10,-1};
  int i,result;

  for(i=0;in1[i]!=-1;i++){
    result=combination(in1[i],in2[i]);
    printf("combination(%d,%d)=%d: ",in1[i],in2[i],result);
    if(out[i]==result){
      printf("Ok\n");
    }else{
      printf("NG\n");
    }
  }
  return 0;
}

第2回

演習2-1

1. # define EOF (-1)

2. extern int getchar (void);

3. extern int printf (__const char *__restrict __format, ...);

演習2-2

略

演習2-3

略

演習2-4

略

第3回

演習3-1

1
2
1
2
2
0
2

第4回

演習4-1

略

演習4-2

低速版

#include <stdio.h>
int fibo(int n){
  if(n==0){ return 1; }
  if(n==1){ return 1; }
  return fibo(n-1)+fibo(n-2);
}
int main(void){
  printf("%d\n",fibo(45));
  return 0;
}

高速版

#include <stdio.h>
#include <stdlib.h>
#define N 100
int a[N]={0};
int fibo(int n){
  if(n>=N){fprintf(stderr,"Overflow at %d\n",n);exit(2);}
  if(a[n]>0){ return a[n];}
  if(n==0){ return 1; }
  if(n==1){ return 1; }
  a[n]=fibo(n-1)+fibo(n-2);
  return a[n];
}
int main(void){
  printf("%d\n",fibo(45));
  return 0;
}

演習4-3

低速版

#include <stdio.h>
int ack(int n, int m){
  if(n==0){return m+1;}
  if(m==0){return ack(n-1,1);}
  return ack(n-1, ack(n,m-1));
}
int main(void){
  int i;
  for(i=0;i<=4; i++){
    printf("ack(%d,1)=%d\n",i,ack(i,1));
  }
  return 0;
}

高速版

#include <stdio.h>
#include <stdlib.h>
#define MAX 100000
int a[5][MAX]={0};
int ack(int n, int m){
  if(m>=MAX){fprintf(stderr,"Overflow! m=%d\n",m);exit(2);}
  if(a[n][m]!=0){return a[n][m];}
  if(n==0){a[n][m]=m+1;}
  else if(m==0){a[n][m]= ack(n-1,1);}
  else {a[n][m]=ack(n-1, ack(n,m-1));}
  return a[n][m];
}
int main(void){
  int i;
  for(i=0;i<=4; i++){
    printf("ack(%d,1)=%d\n",i,ack(i,1));
  }
  return 0;
}

演習4-4

#include <stdio.h>
void hanoi(int n, char x, char y, char z){
  if(n==1){
    printf("move 1 from %c to %c\n",x,y);
    return;
  }
  hanoi(n-1,x,z,y);
  printf("move %d from %c to %c\n",n,x,y);
  hanoi(n-1,z,y,x);
}
int main(void){
  hanoi(4,'a','b','c');
  return 0;
}

演習4-5

void Turtle::home(int xsize, int ysize){
  x=static_cast<double>(_x);
  y=static_cast<double>(_y);
  angle=0.0;
}
void Turtle::forward(int n){
  line(x,y,x+=n*cos(angle*3.141592/180),y+=n*sin(angle*3.141592/180));
}
void Turtle::turn(double dangle){
  angle += dangle;
}
void Turtle::skip(int n){
  x+=n*cos(angle*3.141592/180);
  y+=n*sin(angle*3.141592/180);
}

演習4-6

box.cpp を次のように書き換える。

1. Box::drawBox() の前に tree() をコピーする。
2. Box::drawBox() を下記のように書き換える

   
   BOOL Box::drawBox()
   {
       Turtle t(hwnd);
       t.home(x_size/2,y_size/2);
       tree(t,50);
       return TRUE;
   }
   

したがって、 box.cpp は次のようになる。

//box.cpp
#include <Windows.h>
#include "box.hpp"
#include "turtle.hpp"
BOOL Box::init( HWND hwnd)
{
    HDC hdc = GetDC(hwnd);
    TEXTMETRIC tm;
    GetTextMetrics(hdc, &tm);
    ReleaseDC(hwnd, hdc);
    y_size = static_cast<int>(
    static_cast<double>(YSIZE)/8.0*tm.tmHeight);
    x_size = static_cast<int>(
    static_cast<double>(XSIZE)/4.0*tm.tmAveCharWidth);
    return TRUE;
}
void tree(Turtle &t, int length){
  if(length < 1){
    t.turn(180);
    return;
  }
  t.forward(length);
  t.turn(30); tree(t, length/2);
  t.turn(120); tree(t, length/2);
  t.turn(30); t.skip(length);
  return;
}
BOOL Box::drawBox(HWND hwnd, int size){
    Turtle t(hwnd);
    t.home(x_size/2,y_size/2);
    tree(t,50);
    return TRUE;
}
BOOL Box::command(HWND hwnd, WPARAM wp)
{
  if(LOWORD(wp)==IDCANCEL){
      EndDialog( hwnd, -1);
      return TRUE;
  }
  return FALSE;
}

さらに Box という名前は正確に内容を表さなくなってしまったので、 Tree などに書き換えが必要であるが、書き換えに関しては割愛する。

演習4-7

演習 4-6 と同様にする。

//box.cpp
#include <Windows.h>
#include "box.hpp"
#include "turtle.hpp"
BOOL Box::init( HWND hwnd)
{
    HDC hdc = GetDC(hwnd);
    TEXTMETRIC tm;
    GetTextMetrics(hdc, &tm);
    ReleaseDC(hwnd, hdc);
    y_size = static_cast<int>(
    static_cast<double>(YSIZE)/8.0*tm.tmHeight);
    x_size = static_cast<int>(
    static_cast<double>(XSIZE)/4.0*tm.tmAveCharWidth);
    return TRUE;
}

void koch(Turtle &t, int length, int degree){
  if(degree<=1){
    t.forward(length);
    return;
  }
  koch(t,length/3,degree-1);
  t.turn(-60);
  koch(t,length/3,degree-1);
  t.turn(120);
  koch(t,length/3,degree-1);
  t.turn(-60);
  koch(t,length/3,degree-1);
  return;
}
BOOL Box::drawBox(HWND hwnd, int size){
    Turtle t(hwnd);
    t.home(x_size/2,y_size/2);
    koch(t,100,4);
    return TRUE;

}
BOOL Box::command(HWND hwnd, WPARAM wp)
{
  if(LOWORD(wp)==IDCANCEL){
      EndDialog( hwnd, -1);
      return TRUE;
  }
  return FALSE;
}

第5回

演習5-1

略

演習5-2

略

演習5-3

略

演習5-4

stack.h

typedef struct st {
  char *string;
  struct st *pointer;
} stack;
int empty(void);
int push(char * x);
char * pop(void);

stack.c

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
stack *stackpointer=NULL;
int empty(void){
  return stackpointer==NULL;
}
int push(char * x){
  stack *next=malloc(sizeof(stack));
  if(next==NULL){ /* メモリが確保できないと NULL が返される */
    return 0;
  }
  next->string = x;
  next->pointer=stackpointer;
  stackpointer=next;
  return 1;
}
char * pop(void){
  char * x=stackpointer->string;
  stack *p=stackpointer;
  stackpointer=p->pointer;
  free(p);
  return x;
}

parser.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"

void error(int i){
  fprintf(stderr,"error %d\n",i);
  exit(i);
}
char * buffer_base;
char * buf_pointer;
void store_buffer(char c){
  *buf_pointer=c;
  buf_pointer++;
}
void set_buffer(char *p){
  buffer_base=p;
}
void reset_buffer(void){
  buf_pointer=buffer_base;
}
void push_buffer(){
  char * newstr;
  if((newstr=strdup(buffer_base))==NULL){
    error(4);
  }	  
  push(newstr);
  printf("%s pushed\n",q);
}
int endoftag(char c){
  return (c==' ')||(c=='>');
}
int compare_buffer_stack(void){
  char * str;
  int result; 
  if(empty()){error(1);}/* 開始タグ無し */
  str=pop();
  printf("%s popped\n",str);
  result=strcmp(str,buffer_base+1);
  free(str);
  return result;
}
int end_tag(void){
  return *buffer_base=='/';
}
int main(void){
  int flag=0;
  int l;
  char buffer[50];
  char c;
  set_buffer(buffer);
  while((c=getchar())!=EOF){
    if(flag && endoftag(c)){/* flag==1 タグ内解析中 */
      store_buffer('\0');
      if(end_tag()){ /* 終了タグ処理 */
        if(compare_buffer_stack()!=0){
          error(2); /* 不一致 */
        }
        flag=0;
      }else{ /* 開始タグ処理(プッシュ) */
        push_buffer();
      }
    }else if(flag && ! endoftag(c) { /* タグの要素名の採集 */
      store_buffer(c);
    }else if(!flag){ /* flag==0 タグの外 */
      if(c=='<'){
        reset_buffer();
	flag=1;
      }
    }
  }
  if(!empty()){
    error(3);
  }
  printf("Ok.\n");
  return 0;
}

Makefile

TARGET = parser
$(TARGET):	parser.o stack.o
	$(CC) -o $@ $^
stack.o:	stack.h
parser.o:	stack.h

test0.xml(Ok)

<body>
<h1>解答集</h1>
<h2>目次</h2>
<ul>
<li><a href="#1">第1回</a></li>
<li><a href="#2">第2回</a></li>
<li><a href="#3">第3回</a></li>
<li><a href="#4">第4回</a></li>
<li><a href="#5">第5回</a></li>
</ul>
</body>

test1.xml(error 1)

<h1>解答集</h1>
<h2>目次</h2>
<ul>
<li><a href="#1">第1回</a></li>
<li><a href="#2">第2回</a></li>
<li><a href="#3">第3回</a></li>
<li><a href="#4">第4回</a></li>
<li><a href="#5">第5回</a></li>
</ul>
</body>

test2.xml(error 2)

<body>
<h1>解答集</h1>
<h2>目次</h2>
<ul>
<li><a href="#1">第1回</a></li>
<li><a href="#2">第2回</a></li>
<li><a href="#3">第3回</li></a>
<li><a href="#4">第4回</a></li>
<li><a href="#5">第5回</a></li>
</ul>
</body>

test3.xml(error 3)

<body>
<h1>解答集</h1>
<h2>目次</h2>
<ul>
<li><a href="#1">第1回</a></li>
<li><a href="#2">第2回</a></li>
<li><a href="#3">第3回</a></li>
<li><a href="#4">第4回</a></li>
<li><a href="#5">第5回</a></li>
</ul>

error 4 はメモリーオーバーなのでテストデータは作らず

演習5-5

#include <stdio.h>
#include <stdlib.h>
typedef struct st {
  int num;
  struct st *pointer;
} stack;
stack *stackpointer=NULL;
int empty(void){
  return stackpointer==NULL;
}
int push(int x){
  stack *next=(stack *) malloc(sizeof(stack));
  if(next==NULL){ /* メモリが確保できないと NULL が返される */
    return 0;
  }
  next->num = x;
  next->pointer=stackpointer;
  stackpointer=next;
  return 1;
}
int pop(void){
  int x=stackpointer->num;
  stack *p=stackpointer;
  stackpointer=p->pointer;
  free(p);
  return x;
}
int main(void){
  char *p;
  char first;
  int i;
  int x,y;
  char *formula[] ={"2","3","*","4","5","*","+",NULL};
  for(i=0; formula[i]!=NULL; i++){
    first=*(formula[i]);
    switch(first){
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':
      push(atoi(formula[i]));
      break;
    case '+':
      y=pop();
      x=pop();
      push(x+y);
      break;
    case '*':
      y=pop();
      x=pop();
      push(x*y);
      break;
    }
  }
  printf("%d\n",pop());
  return 0;
}

第6回

演習6-1

14種類

演習6-2

演習6-3

n 頂点の場合、他の n-1 頂点とそれぞれ結ぶには、 n 個の中から 2 個取り 出す場合の数になるので、 $\frac{n\left(n-1\right)}{2}$ 。

演習6-4

n 頂点それぞれについて、 m 個の頂点と辺を結ぶので、 mn。

演習6-5

頂点数は n 個。辺の数は最大で完全グラフになるので、 $\frac{n\left(n-1\right)}{2}$ 。 したがって、 $n+\frac{n\left(n-1\right)}{2}=\frac{n\left(n+1\right)}{2}$ 。

演習6-6

演習6-7

1. 行う計算はx*xのみ。 従って、 $O(logx)$ 。

2. $x!$ の大きさは高々 $x^x$ 程度。 従って、for の中の f*=i の計算には $O(xlogx)$ の計算時間がかかる。 for は x-1 回繰り返すので、全体では。 $O(x^{2}logx)$ 。

第7回

演習7-1

#include <iostream>
#include <fstream>
#include <list>
#include <string>
class Line {
private:
  const static int maxline = 24;
  std::list<std::string> line;
  std::list<std::string>::iterator begin,end,pagetop;
public:
  void initialize();
  void down();
  void up();
  void bottom();
  void top();
  friend std::ifstream& operator>>(std::ifstream& ifs, Line& l);
  friend std::ostream& operator<<(std::ostream& os, const Line& l);
};
void Line::down(){
  for(int i=0; i< maxline && pagetop!=end; ++i){
    ++pagetop;
  }
}
void Line::bottom(){
  pagetop=end;
}
void Line::top(){
  pagetop=begin;
}
void Line::up(){
  for(int i=0; i< maxline && pagetop!=begin; ++i){
    --pagetop;
  }
}
void Line::initialize(){
  begin=line.begin();
  end=line.end();
  top();
}  
std::ifstream& operator>>(std::ifstream& ifs, Line& l){
  std::string buf;
  while(!ifs.eof()){
    getline(ifs,buf);
    l.line.insert(l.line.end(),buf);
  }
  return ifs;
}
std::ostream& operator<<(std::ostream& os, const Line& l){
  int i;
  std::list<std::string>::iterator li;
  for(i=0, li=l.pagetop; li!=l.end && i<l.maxline ; ++li, ++i){
    os << *li << std::endl;
  }
  return os;
}
int main(int argc, char* argv[]){
  if(argc!=2){
    std::cerr << "Usage: " << argv[0] << " filename" << std::endl;
    return 1;
  }
  std::ifstream input(argv[1]);
  if(!input){
    std::cerr << "Can not open " << argv[1] << std::endl;
    return 2;
  }
  Line line;
  input >> line;
  line.initialize();
  char c;
  for(;;){
    std::cout << line;
    std::cin >> c;
    switch(c){
    case 'q': 
      return 0;
      break;
    case 'd': 
      line.down();
      break;
    case '>':
      line.bottom();
    case 'u': 
      line.up();
      break;
    case '<':
      line.top();
      break;
    default:
      break;
    }
  }
}

第8回

演習8-1

14種類

演習8-2

1. main 関数中の show();の後に showstructure(t,""); を付け加える。

   : 100
   l: 62
   lr: 85
   lrl: 73
   lrr: 85
   

2. 

演習8-3

partition(0,9)

1. s=7
2. f=0, t=8 → 5, 10, 3, 6, 1, 9, 2, 4, 7, 8, -1
3. f=1, t=8 → 5, 7, 3, 6, 1, 9, 2, 4, 10, 8, -1
4. f=1, t=7 → 5, 4, 3, 6, 1, 9, 2, 7, 10, 8, -1
5. f=5, t=7 → 5, 4, 3, 6, 1, 7, 2, 9, 10, 8, -1
6. f=5, t=6 → 5, 4, 3, 6, 1, 2, 7, 9, 10, 8, -1
7. f=6, t=6 → 5, 4, 3, 6, 1, 2, 7, 9, 10, 8, -1

partition(0,6)

1. s=5
2. f=0, t=5 → 2, 4, 3, 6, 1, 5, 7, 9, 10, 8, -1
3. f=3, t=5 → 2, 4, 3, 5, 1, 6, 7, 9, 10, 8, -1
4. f=3, t=4 → 2, 4, 3, 1, 5, 6, 7, 9, 10, 8, -1
5. f=4, t=4 → 2, 4, 3, 1, 5, 6, 7, 9, 10, 8, -1

partition(0,4)

1. s=2
2. f=0, t=3 → 1, 4, 3, 2, 5, 6, 7, 9, 10, 8, -1
3. f=1, t=3 → 1, 2, 3, 4, 5, 6, 7, 9, 10, 8, -1
4. f=1, t=1 → 1, 2, 3, 4, 5, 6, 7, 9, 10, 8, -1

partition(0,1)

1. s=1
2. f=0, t=0 → 1, 2, 3, 4, 5, 6, 7, 9, 10, 8, -1

partition(0,0)

partition(1,1)

partition(2,4)

1. s=3
2. f=2, t=2 → 1, 2, 3, 4, 5, 6, 7, 9, 10, 8, -1

partition(2,2)

partition(3,4)

1. s=4
2. f=3, t=3 → 1, 2, 3, 4, 5, 6, 7, 9, 10, 8, -1

partition(3,3)

partition(4,4)

partition(5,6)

1. s=6
2. f=5, t=5 → 1, 2, 3, 4, 5, 6, 7, 9, 10, 8, -1

partition(5,5)

partition(6,6)

partition(7,9)

1. s=9
2. f=7, t=9 → 1, 2, 3, 4, 5, 6, 7, 8, 10, 9, -1
3. f=8, t=9 → 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -1
4. f=8, t=8 → 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -1

partition(7,8)

1. s=8
2. f=7, t=7 → 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -1

partition(7,7)

partition(8,8)

partition(9,9)

演習8-4

3種類

第9回

演習9-1

1. a で始まるファイル名

dir a*.*

2. 拡張子が exe のファイル名

dir *.exe

3. 前の部分のファイル名が d で終るファイル名

dir *d.*

演習9-2

1. a で始まる文字列

a.*

2. a を含む文字列

.*a.*

3. 英字で始まり、残りは英字と数字だけの文字列

\p{Alpha}\p{Alnum}+

演習9-3

1. a*

a で始まる文字列

2. [abc]

a または b または c

3. <[^>]*>

< と < の中に文字列が入っているもの。(> を含まない)

4. [1-9][0-9]*

0 を含まない自然数

演習9-4

1. 先頭が a で始まる文字列

a.*

2. 最後が b で終る文字列

.*b

3. c を含む文字列

.*c.*

4. abc を含む文字列

.*abc.*

5. abc または def を含む文字列

.*(abc|def).*

6. 先頭が英字または_(アンダースコア)、二文字目以降がある場合、英字、 数字、または_(アンダースコア)である文字列(C 言語では名前はこのルールに 従う必要がある)

(\p{Alpha}|_)(\p{Alnum}|_)*

演習9-5

1. Java の表現で、整数を表しなさい

-?[1-9][0-9]*

2. 次の文字列中の整数を列挙するプログラムを作りなさい

import java.util.regex.*;
class NumEnu {
  public static void main(String[] args){
    String input="-10+30-20";
    Pattern p = Pattern.compile("-?[1-9][0-9]*");
    Matcher m = p.matcher(input);
    while(m.find()){
      System.out.println(m.group());
    }
  }
}

3. input 文字列に含まれている整数の数を表示するプログラムを作りな さい

import java.util.regex.*;
class NumCount {
  public static void main(String[] args){
    String input="-10+30-20";
    Pattern p = Pattern.compile("-?[1-9][0-9]*");
    Matcher m = p.matcher(input);
    int i=0;
    while(m.find()){
     i++;
    }
    System.out.println(i);
  }
}

演習9-6

1. 次の文字列中の整数を列挙するプログラムを作りなさい char inputstring[]="-10+30-20";

numenu.l

%{
#undef YY_INPUT
#define YY_INPUT(b, r, ms) (r=my_input(b,ms))
%}
%%
-?[1-9][0-9]* { printf("%s\n",yytext);}
. ;
%%
char inputstring[]="-10+30-20";
char* ptr;
extern int my_input();
int my_input(char *buf, int max_size)
{
  int n;
  n = strlen(ptr);
  if(n>max_size){ n=max_size; }
  if (n>0){
    strncpy(buf, ptr, n);
    ptr +=n;
  }
  return n;
}
int main(void){
  ptr=inputstring;
  yylex();
  return 0; 
}

Makefile

TARGET=numemu
LEX=flex
$(TARGET): lex.yy.c
	$(CC) -o $@ $^ -lfl 
lex.yy.c: $(TARGET).l
	$(LEX) $^

2. input 文字列に含まれている整数の数を表示しなさい

%{
#undef YY_INPUT
#define YY_INPUT(b, r, ms) (r=my_input(b,ms))
int i=0;
%}
%%
-?[1-9][0-9]* { i++;}
. ;
%%
char inputstring[]="-10+30-20";
char* ptr;
extern int my_input();
int my_input(char *buf, int max_size)
{
  int n;
  n = strlen(ptr);
  if(n>max_size){ n=max_size; }
  if (n>0){
    strncpy(buf, ptr, n);
    ptr +=n;
  }
  return n;
}
int main(void){
  ptr=inputstring;
  yylex();
  printf("%d\n",i);
  return 0;
}

演習9-7

1. または
2. または
3. または
4. あたえられた正規表現は任意の文字列にマッチしてしまうので、正直に変換せ ず、次で十分である。

第10回

演習10-1

オートマトン

プログラム

#include <stdio.h>
typedef enum status {
  STATE1, STATE2, ERROR, ACCEPT}
STATE;
int get(void){
  int c;
  while((c=getchar())=='\n');
  return c;
}
int main(void){
  int c;
  STATE s;
  s=STATE1;
  while((c=get())!=EOF){
    switch(s){
    case STATE1:
      if((c>='1')&&(c<='9')){ s=STATE2; }
      else{ s=ERROR; }
      break;
    case STATE2:
      if((c>='0')&&(c<='9')){ s=STATE2; }
      else{ s=ERROR; }
      break;
    case ERROR:
      printf("reject\n");
      return 2;
    }
  }
  if(s==STATE2){
    printf("accept\n");
    return 0;
  }else{
    printf("reject\n");
    return 2;
  }
}

演習10-2

1. 非決定性オートマトン

   

   決定性オートマトン

   

   プログラム

   
   #include <stdio.h>
   typedef enum st { s1, s12, s13, s14 } STATUS;
   int get(void){
     int c;
     while((c=getchar())=='\n');
     return c;
   }
   int main(void){
     char c;
     int count=0;
     STATUS s=s1;
     while((c=get())!=EOF){
       switch(s){
       case s1:
         if(c=='a'){ s=s12; }
         break;
       case s12:
         if(c=='a'){ s=s12; }
         else if(c=='b'){ s=s13; }
         else { s=s1; }
         break;
       case s13:
         if(c=='a'){ s=s12; }
         else if(c=='b'){ s=s14; count++;}
         else { s=s1; }
         break;
       case s14:
         if(c=='a'){ s=s12; }
         else { s=s1; }
         break;
       }
     }
     printf("%d\n",count);
     return 0;
   }
   

2. 非決定性オートマトン

   
   

   	a	b	c
   1	1,2	1	1
   2		3
   3	4
   4		5
   5

   決定性オートマトン

   
   

   	a	b	c
   1	1,2	1	1
   1,2	1,2	1,3	1
   1,3	1,2,4	1	1
   1,2,4	1,2	1,3,5	1
   1,3,5	1,2,4	1	1

   プログラム

   
   #include <stdio.h>
   typedef enum st { s1, s12, s13, s124, s135 } STATUS;
   int get(void){
     int c;
     while((c=getchar())=='\n');
     return c;
   }
   int main(void){
     char c;
     int count=0;
     STATUS s=s1;
     while((c=get())!=EOF){
       switch(s){
       case s1:
         if(c=='a'){ s=s12; }
         break;
       case s12:
         if(c=='a'){ s=s12; }
         else if(c=='b'){ s=s13; }
         else { s=s1; }
         break;
       case s13:
         if(c=='a'){ s=s124; }
         else { s=s1; }
         break;
       case s124:
         if(c=='a'){ s=s12; }
         else if(c=='b'){ s=s135; count++;} 
         else { s=s1; }
         break;
       case s135:
         if(c=='a'){ s=s124; }
         else { s=s1; }
         break;
       }
     }
     printf("%d\n",count);
     return 0;
   }
   

3. 非決定性オートマトン

   
   

   	a	b	c
   1	1,2	1	1
   2		3
   3		4
   4	5
   5

   決定性オートマトン

   
   

   	a	b	c
   1	1,2	1	1
   1,2	1,2	1,3	1
   1,3	1,2	1,4	1
   1,4	1,2,5	1	1
   1,2,5	1,2	1,3	1

   プログラム

   
   #include <stdio.h>
   typedef enum st { s1, s12, s13, s14, s125 } STATUS;
   int get(void){
     int c;
     while((c=getchar())=='\n');
     return c;
   }
   int main(void){
     char c;
     int count=0;
     STATUS s=s1;
     while((c=get())!=EOF){
       switch(s){
       case s1:
         if(c=='a'){ s=s12; }
         break;
       case s12:
         if(c=='a'){ s=s12; }
         else if(c=='b'){ s=s13; }
         else { s=s1; }
         break;
       case s13:
         if(c=='a'){ s=s12; }
         else if(c=='b'){ s=s14; }
         else { s=s1; }
         break;
       case s14:
         if(c=='a'){ s=s125; count++; }
         else { s=s1; }
         break;
       case s125:
         if(c=='a'){ s=s12; }
         else if(c=='b'){ s=s13; }
         else { s=s1; }
         break;
       }
     }
     printf("%d\n",count);
     return 0;
   }
   

演習10-3

製作中

演習10-4

製作中

第11回

演習11-1

S→0, S→-K, S→εK, K→1L, K→2L, K→3L, K→4L, K→5L, K→6L, K→7L, K→8L, K→9L, L→ε, L→0L, L→1L, L→2L, L→3L, L→4L, L→5L, L→6L, L→7L, L→8L, L→9L

演習11-2

作成中

演習11-3

1. In my case, it's eel one.
2. In my doughter's case, it was a boy.

演習11-4

S→[S] を追加する。

演習11-5

規則を以下に差し替える。

wa: wa '+' atai { $$ = $1 + $3;}
  | atai        { $$ = $1;}
;
atai: '(' wa ')' { $$ = $2;}
    | KAZU {$$ = $1;}

第12回

演習12-1