문제

this is the language:

L = { w belong {a,b,c}* | |w|= 3 * number(a) (w) }

Then, what does that mean?

도움이 되었습니까?

해결책

It means that L is the language of strings w consisting of symbols 'a', 'b'' and 'c', where the length of the string w equals to 3 times the number of symbol 'a' present in the string w.

The productions for this grammars should be such that if it add one 'a' then it also adds two 'b', or two 'c', or one 'b'; one 'c'. Check below grammar:

S → ^ | SaSMSM |  SMSaSM | SMSMSa   
M → b | c

here ^ means epsilon.

To generate aabbcc use Right most derivation

  1. S → SaSMSM
  2. replace first S in rhs by ^ using S → ^
    S → SaSMSM → aSMSM
  3. replace S → SaSMSM
    S → SaSMSM → aSaSMSMMSM
  4. use S → ^
    S → SaSMSM → aSaSMSMMSM → aaSMSMMSM
  5. use S → ^
    S → SaSMSM → aSaSMSMMSM → aaSMSMMSM → aaMSMMSM
  6. M → b
    S → SaSMSM → aSaSMSMMSM → aaSMSMMSM → aaMSMMSM → aabSMMSM
  7. use S → ^
    S → SaSMSM → aSaSMSMMSM → aaSMSMMSM → aaMSMMSM → aabSMMSM → aabMMSM
  8. M → b
    S → SaSMSM → aSaSMSMMSM → aaSMSMMSM → aaMSMMSM → aabSMMSM → aabMMSM → aabbMSM
  9. M → c
    S → SaSMSM → aSaSMSMMSM → aaSMSMMSM → aaMSMMSM → aabSMMSM → aabMMSM → aabbMSM → aabbcSM
  10. use S → ^
    S → SaSMSM → aSaSMSMMSM → aaSMSMMSM → aaMSMMSM → aabSMMSM → aabMMSM → aabbMSM → aabbcSM → aabbcM
  11. M → c
    S → SaSMSM → aSaSMSMMSM → aaSMSMMSM → aaMSMMSM → aabSMMSM → aabMMSM → aabbMSM → aabbcSM → aabbcM → aabbcc

다른 팁

S -> aBCS | aBC
S -> BCaS | BCa
S -> BaCS | BaC
S -> aCBS | aCB
S -> CaBS | CaB
S -> CBaS | CBa
B -> b
C -> c

may be right ?

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top