2012-07-27 19 views
1

이 있다면 Σ*에 어떤 단어가 있습니까?Σ * 및 Σ을 공식 언어로 이해하기

Σ*= {a,aa,aaa,aaaa.....}?

감사

+3

빈 문자열을 포함해야합니다. –

+0

로젠의 책을 바탕으로 한이 발표는 유용 할 수도 있습니다 http://www.cis.temple.edu/~latecki/Courses/CIS166-05/Lectures/ch11.1.ppt – arunmoezhi

답변

2

Σ*= {#, a,aa,aaa,aaaa.....}은 빈 문자열 # (phi)을 포함하여 모든 가능한 n* a을 의미한다. 그 시퀀스를 만드는 또 다른 방법은 문법을 사용하는 것입니다 :

S -> S 
S -> aS 
S -> # 

여기서 #은 빈 문자열입니다.

2

그것은 당신이 언급하지 않았다 빈 문자열을 가지고, 또한 모든 길이의 시퀀스가 ​​포함되어 있습니다.

자세한 내용은 http://en.wikipedia.org/wiki/Kleene_star에서 확인할 수 있습니다.

+0

^i, i = 1 ........ INF – ron

1

Σ*에있는 *은 일반적으로 0 또는 여러 번을 나타냅니다. 따라서 Σ*은 빈 문자열과 알파벳 Σ의 문자 조합을 갖습니다.

(당신의 알파벳 만 a을 가지고 있기 때문에, 다음 Σ*a 빈 문자열의 조합을해야합니다.)

당신의 알파벳 이상의 값은 다음 a의 조합을 것 Σ = {a,b}을 즉했다면

b 빈 문자열 당신의 알파벳 Σ={a} 경우 즉 Σ* = {phi, a, b, aa, ab, ba, bb, bab, ...(etc)}

0

Σ*Σ (none 포함)에서 가져온 기호를 임의의 수만큼 연결하여 만들 수있는 길이의 문자열 집합입니다.

Σ^nΣ 이상 길이 n의 문자열의 집합하자 :

여기 Σ*을 정의 할 수있는 한 가지 방법입니다. 이어서

Σ * = Σ^0^Σ 조합 조합 1 ...

Σ^0 = {phi} 피 길이 0 유일한 문자열 때문이다. 그러므로 φ에 상관없이 Σ이든 상관 없습니다.