Peter Linz Exercise 7.3

Question

#3 : Is the language L= { aⁿbⁿ : n>=1 } U {b} deterministic ?

#4 : Is the language L={aⁿbⁿ : n>=1} U {a} deterministic ?

#7 Is the following regular language deterministic?

  L= { aⁿb^mc^k : n=m or m=k }

#8 Is the L = {aⁿb^m : n=m or n=m+2} deterministic?

#9 Is the language {wcw^R : w ∈ {a,b}^* }  deterministic?

#10 Is the language L = {wwR : w ∈ {a,b}^* } deterministic?

#11 An example  of a deterministic context-free language whose reverse is not deterministic?

My Analysis is as follows :

#3 : Non-deterministic as for one b we would go to another state which would indicate that only one b is there which accepts the  {b} part of the language. And if we see one a, then we would watch for aⁿbⁿ.

#4 : Non-deterministic : Same reason as for 3

#7   L= { aⁿb^mc^k : n=m or m=k } can be broken down as follows :

     L = { aⁿbⁿc^k } U {aⁿb^mc^m}

This is non-deterministic, as looking at the number of a's our PDA can determine that a string belongs to which part of the language and will make transitions accordingly. That is, whether to check for equivalence for a and b or to check for equivalence of b and c.

#8. L = {aⁿb^m : n=m or n=m+2} can be broken down as follows :

   L = {aⁿbⁿ } U {aⁿbⁿ⁺²}

Non-deterministic as by looking at the number of a's, our PDA has to decide(Non-determinism) that a string has either equal number of a's or number of a's are 2 less than the number of b's that appear after it.

#9. L= {wcw^R : w ∈ {a,b}^* }

 deterministic as c would act as an indicator after which our PDA can start to pop off from the stack corresponding to each input symbol that appears after c.Here our PDA knows exactly when to push and when to pop off values from the stack.

#10 L = {ww^R : w ∈ {a,b}^* }

Non-Deterministic as there is no central point after which our PDA can decide that W has ended and W^R has started.

#11- No Idea about it.

Please someone verify and tell me is my way of analysis and the analysis is correct or not?

Answer 1

3 is determinstic and also 4

reason:

for example as the language is cfl, so if it is deterministic  according to the definition, if in PDA of a cfl , each transition has only One state to go always that is deterministic.

now the language can be anything {abb,aabbb,aaabbbb...}

whenevr we see an A we loop and push an A in stack and Whenever we encounter B we match it and if we see an A on top of stack we pop it.. and when the stack becomes empty ,then if we encounter a B , we go to accepting state

Now here are two different transition

{b, tos(a)}->then pop

{b,tos(empty)}->then go to ACC

so it is deterministic

but for all transitions there is only one choice..

tell me if you need more clear explanation :D

answer for Q11

L={{aⁿbⁿ : n>=1} U {a^m m>=1}} is deterministic but the reversal of it {a^m m>=1}}U{aⁿbⁿ } is non deterministic because  whenever we encounter an A we may have to loop for first a^m .and for the same A transition we have to go to next state where we have to perform push and pop for the second part of Union.....

Comments

I think first one is deterministic as when u encounter a u have to push on to stack after that on for every b u have to pop a from stack and firstly u encounter b u have to skip only  nw for 2nd question there is non determinism becoz whenever u encounter a u have to decide whether to push it on to stack or just skip it so 2nd one is non determinism

---

#3 and #4 @No_name gave better explanation

#7 It is non-deterministic because at the beginning you cannot decide which pattern to look for i.e. m=n or m=k and you cannot look for both because you will loose count in DPDA of one of the letters a,b or c.

#8 It is deterministic. You can easily draw a DPDA. i)Draw DPDA for aⁿbⁿ. ii)Draw two more states at the end that accept 2 extra b's without pushing anything on stack.

#9 and #10 Correct explanation.

#11 L₁={aⁿbⁿ:n>=0}  L₂={aⁿb²ⁿc:n>=0} L₁UL₂ is non deterministic. But reverse is {bⁿaⁿ}U{cb²ⁿaⁿ} is deterministic because you can decide by looking at first letter to look for what pattern (i.e. if first letter is b then bⁿaⁿ else if first character is c then b²ⁿaⁿ. This example was given in instructor manual of Peter Linz.

Answer 2

3 and 4 are deterministic bcz we can make a DPDA.

Answer 3

correct

Comments

all correct? :O

---

for question 11..http://stackoverflow.com/questions/8363833/find-a-non-deterministic-cfl-whose-reverse-is-deterministic this may help you..

Answer 4

#3 should be deterministic