Formal Languages - Grammar -

i taking formal languages , computability class , having little trouble understanding concept of grammar. 1 of assignment questions this:

take ∑ = {a,b}, , let n_a(w) , n_b(w) denote number of a's , b's in string w, respectively. grammar g productions:

s -> ss s -> λ s -> asb s -> bsa 

generates language l = {w: n_a(w) = n_b(w)}.

1) language in example contains empty string. modify given grammar generates l - {λ}.

• i thinking should modify condition of l, like:

  l = {w: n_a(w) = n_b(w), n_a, n_b > 0}

  that way, indicate string never empty.

2) modify grammar in example generate l ∪ {aⁿbⁿ⁺¹: n >= 0}.

• i not sure on how one. should mean make 1 more condition in grammar, adding s -> asbb?

any explanation these 2 questions appreciated. i'm still trying figure these grammar stuff out not sure answers.

1) question modifying grammar obtain new language; don't modify directly language…

your grammar generates empty word because of production:

s -> λ 

so think of removing production altogether. yields following grammar:

s -> ss s -> asb s -> bsa 

unfortunately, grammar doesn't generate language (a bit in induction, misses initial: there no productions consist of terminals). fix this, add following productions:

s -> ab s -> ba 

2) don't randomly try add production rules in hope it's going work. here want a's followed b's. production rule

s -> bsa 

must disappear. also, rule

s -> ss 

would produce, e.g., abab (try see how obtained). we'll have remove too. we're left with:

s -> λ s -> asb 

now grammar generates:

λ ab aabb aaabbb 

etc. that's not bad @ all! trailing b, create new non-terminal, t, replace our current s t, , add trailing b in s:

t -> λ t -> atb s -> tb 

---

i know homework; gave solutions homework: that's because, way asked question, seems you're lost. hope answer on right path!