請問怎麼看grammar的型態啊？
1. S->A,S->C,A->aA,A->aB,B->aBb,B->ab,C->Cb,C->Bb
這個為什麼是type-2呢？我覺得是regular說？type-2不是後面接兩個大寫以上嗎？
2. S->aA,A->aAb,A->λ
這個為什麼是type-2?
3. S->aAB,AB->bB,B->b,A->aB
4. S->aAB,AB->c,A->b,B->AB
3跟4要怎麼看呢？因為有點搞混了，有人可以教一下嗎？謝謝。
5.Construct the state diagram of a Mealy machine with minimum number of
states to implement an even parity generator where the input χ is a one-bit
signal,and the output ρ produces 1 if there are odd number of 1s so far, and
0 otherwise.
ans state| 0 1 | 0 1
s0 s0 s1 0 1
s1 s1 s0 1 0
這題答案有點怪怪偶同位不是算是不是偶數個1嗎？
這題目不是求若奇數個1就output 1嗎？我若輸入0110跟0101答案會不同咧
是不是這個答案有問題？
6.Give a grammar that specifies the following language:
L={a^iba^j|i≧1,j≧0}
答案這樣寫可以嗎？ S->aS,S->bA,A->aA,A->λ
7.Show that the language L={a^k | k=i^2,i≧1} is not a finite state language.
為什麼是取iεZ^+使得(i+1)^2 - i^2 > N,考慮α=a^(i+1)^2 ε L
上面這句話不懂為什麼這麼取，有人可以解說一下嗎？謝謝。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.64.173.161