[프로그래밍언어론] regular language

1.

ab* b는 0 ~ 무한대까지 나올 수 있다.

 

(0 + 1)* +는 or여서 0과 1의 조합을 모두 적을 수 있다.

 

(0 + 1)*00 위의 모든 조합에서 마지막에 00이 붙는다.

 

(aa)*는 아무것도 없거나 aa , aaaa , aaaaaa... 처럼 짝수로 오르겠죠잉?

 

x = ax + b의 의미는 x -> ax | b 이걸 실제로 해보면 계속 aaaa...b가 되기때문에 x = a*b라고 한다.

다시, x = ax + b와 x -> ax | b 는 x = a*b와 같다.

 

검사하는 방법:: x= ax+b에 x = a*b를 넣는다.

(참고. a^+ + 입실론 = a*)

 

 

2.

예시

G = ( {S,R}, {a,b}, P, S)이고 regular expression L(G)는? (P는 S -> aS + bR + 입실론 그리고 R -> aS 정의 되어 있다.)

S = as+br+입실론 그리고 R = as