解答集

目次

第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;
  }else{
    hanoi(n-1,x,z,y);
    printf("move %d from %c to %c\n",n,x,y);
    hanoi(n-1,z,y,x);
    return ;
  }
}
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){
  double dx,dy;
  dx=n*cos(angle*3.141592/180);
  dy=n*sin(angle*3.141592/180);
  line(x,y,x+=dx,y+=dy);
}
void Turtle::turn(double dangle){
  angle += dangle;
}
void Turtle::skip(int n){
  double dx,dy;
  dx=n*cos(angle*3.141592/180);
  dy=n*sin(angle*3.141592/180);
  x+=dx;
  y+=dy;
}

演習4-6

tree.cpp
  1. box.cpp を tree() の前にコピーする。
  2. box.h を読み込む部分を tree.h にする。
  3. tree のプロトタイプを作る。
  4. case WM_PAINT の部分を tree を呼ぶようにする。

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


#include <Windows.h>
#include "box.h"
#include "turtle.h"
void tree(Turtle &t, int length);
BOOL CALLBACK box( HWND, UINT, WPARAM, LPARAM );
int x_size, y_size;

int WINAPI WinMain( HINSTANCE hInstance, HINSTANCE, LPSTR, int)
{
  DialogBox( hInstance, "DLG_DATA", HWND_DESKTOP, static_cast<DLGPROC>(box) ) ;
  return 0;
}

BOOL CALLBACK box( HWND hwnd, UINT msg, WPARAM wp, LPARAM lp)
{
  static HWND hwnd_gr;

  switch(msg){
  case WM_INITDIALOG:{
    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;
  }
  case WM_PAINT:{
    Turtle t(hwnd);
    t.home(x_size/2,y_size/2);
    tree(t,50);
    return TRUE;
  }
  case WM_COMMAND:
    switch(LOWORD(wp)){
    case IDCANCEL:
      EndDialog( hwnd, -1);
      return TRUE;
    }
  }
  return FALSE;
}
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;
}
tree.h
box.h を単純にコピーする。
tree.rc
box.rc をコピーして、box という単語を tree に置き換える(二箇所)。
Makefile
TARGET=treeにする。

演習4-7

koch.h

#define XSIZE 100
#define YSIZE 100
koch.cpp

#include <Windows.h>
#include "koch.h"
#include "turtle.h"
void koch(Turtle &t, int length, int degree);
BOOL CALLBACK box( HWND, UINT, WPARAM, LPARAM );
int x_size, y_size;

int WINAPI WinMain( HINSTANCE hInstance, HINSTANCE, LPSTR, int)
{
  DialogBox( hInstance, "DLG_DATA", HWND_DESKTOP, static_cast<DLGPROC>(box) ) ;
  return 0;
}

BOOL CALLBACK box( HWND hwnd, UINT msg, WPARAM wp, LPARAM lp)
{
  static HWND hwnd_gr;

  switch(msg){
  case WM_INITDIALOG:{
    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;
  }
  case WM_PAINT:{
    Turtle t(hwnd);
    t.home(x_size/2,y_size/2);
    koch(t,100,4);
    return TRUE;
  }
  case WM_COMMAND:
    switch(LOWORD(wp)){
    case IDCANCEL:
      EndDialog( hwnd, -1);
      return TRUE;
    }
  }
  return FALSE;
}
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;
}
koch.rc

#include <windows.h>
#include "koch.h"

DLG_DATA DIALOG DISCARDABLE 10, 10, XSIZE, YSIZE
STYLE DS_MODALFRAME | WS_POPUP | WS_VISIBLE | WS_CAPTION | WS_SYSMENU
CAPTION "Koch"
FONT 10, "system"
BEGIN
END
Makefile

TARGET = koch
CXX = g++
RESC = windres
RES_INCS = 
LIBS = -lgdi32
.SUFFIXES: .ro .rc
.rc.ro:
	$(RESC) $(RES_INCS) -i $< -o $@ -O coff

$(TARGET).exe: $(TARGET).o $(TARGET).ro turtle.o
	$(CXX) -o $@ $^ $(LIBS)

turtle.o: turtle.h
$(TARGET).ro: $(TARGET).h
$(TARGET).o: $(TARGET).h

第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=(stack *) malloc(sizeof(stack));
  if(next!=NULL){ /* メモリが確保できないと NULL が返される */
    next->string = x;
    next->pointer=stackpointer;
    stackpointer=next;
    return 1;
  }else{
    return 0;
  }
}
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);
}
int main(void){
  int flag=0;
  int l;
  char buffer[50];
  char c;
  char *p,*q;
  while((c=getchar())!=EOF){
    if(flag){  /* flag==1 タグ内解析中 */
      if((c==' ')||(c=='>')){/* 要素名終了 */
	*p='\0';
	flag=0;
	if(buffer[0]=='/'){ /* 終了タグ処理 */
	  if(empty()){error(1);}/* 開始タグ無し */
	  else{
	    q=pop();
	      printf("%s popped\n",q);
	    if(strcmp(q,buffer+1)!=0){
	      error(2); /* 不一致 */
	    }else{
	      free(q);/* Ok */
	    }
	  }
	}else{
	  /* 開始タグ処理(プッシュ) */
	  l=strlen(buffer);
	  if((q=(char *)malloc((l+1)*sizeof(char)))!=NULL){;
            strcpy(q,buffer);
	    push(q);
	    printf("%s pushed\n",q);
	  }else{
	    error(4);
          }
	}
      }else{ /* タグの要素名の採集 */
	*p++=c;
      }
    }else{ /* flag==0 タグの外 */
      if(c=='<'){
	p=buffer;
	flag=1;
      }
    }
  }
  if(empty()){
    printf("Ok.\n");
  }else{
    error(3);
  }
  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 が返される */
    next->num = x;
    next->pointer=stackpointer;
    stackpointer=next;
    return 1;
  }else{
    return 0;
  }
}
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

  1. (+ 1 2)
  2. (+ 1 (* 2 3))
  3. (+ (* 1 2) (* 3 4))

演習6-3

n 頂点の場合、他の n-1 頂点とそれぞれ結ぶには、 n 個の中から 2 個取り 出す場合の数になるので、 n ⁢ n-1 2 。

演習6-4

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

演習6-5

頂点数は n 個。辺の数は最大で完全グラフになるので、 n ⁢ n-1 2 。 したがって、 n + n ⁢ n-1 2 = n ⁢ n+1 2 。

演習6-6

abcd
a 0110
b 1010
c 1101
d 0010

演習6-7

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

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

第7回

演習7-1


#include <iostream>
#include <fstream>
#include <list>
#include <string>
const int maxline = 24;
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;
  }
  std::list<std::string> line;
  std::list<std::string>::iterator li,begin,end,pagetop;
  std::string buf;
  while(!input.eof()){
    getline(input,buf);
    line.insert(line.end(),buf);
  }
  begin=pagetop=line.begin();
  end=line.end();
  char c;
  int i;
  for(;;){
    for(i=0, li=pagetop; li!=end && i<maxline ; li++, i++){
      std::cout << *li << std::endl;
    }
    std::cin >> c;
    switch(c){
    case 'q': 
      return 0;
      break;
    case 'd': 
      for(i=0; i< maxline && pagetop!=end; i++,pagetop++);
      break;
    case '>':
      pagetop=end;
    case 'u': 
      for(i=0; i< maxline && pagetop!=begin; i++,pagetop--);
      break;
    case '<':
      pagetop=begin;
      break;
    default:
      break;
    }
  }
}

第8回

演習8-1

14種類

演習8-2

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

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

演習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:
      fprintf(stderr,"reject\n");
      return 2;
    }
  }
  if(s==STATE2){
    fprintf(stderr,"accept\n");
    return 0;
  }else{
    fprintf(stderr,"reject\n");
    return 2;
  }
}

演習10-2

  1. 非決定性オートマトン
    abbを受理する非決定性オートマトン
    決定性オートマトン
    abbを受理する決定性オートマトン
    プログラム
    
#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. 非決定性オートマトン
    abbを受理する非決定性オートマトン
    abc
    11,211
    23
    34
    45
    5
    決定性オートマトン
    abbを受理する決定性オートマトン
    abc
    11,211
    1,21,21,31
    1,31,2,411
    1,2,41,21,3,51
    1,3,51,2,411
    プログラム
    
#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. 非決定性オートマトン
    abbaを受理する非決定性オートマトン
    abc
    11,211
    23
    34
    45
    5
    決定性オートマトン
    abbを受理する決定性オートマトン
    abc
    11,211
    1,21,21,31
    1,31,21,41
    1,41,2,511
    1,2,51,21,31
    プログラム
    
#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

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科