Draw the state diagram, this has nothing to do with the fact that L is not a CFL

Question

Draw the state diagram, this has nothing to do with the fact that L is not a CFL

Design a state transition diagrams for a (deterministic) Turing machine which recognizes the following language over A -la, b, cj: L {x | num(a,x)=max(num(b, a), num(c, a: = where num(a, x) denotes the number of occurrences of a in the string . Hint: First symbols b can be matched with symbols c to find which are more numerous (and the more numerous symbols are replaced by ""), and then symbols a are matched with "*"

Explanation / Answer

Solution:

>> Design a state transition diagrams for a (deterministic) Turing machine which recognizes the following language over

>>L {zl num(a, z)=max(num(b, z), num(c, z)))

>>where num(a, x) denotes the number of occurrences of a in the string x.

>>means number of a=number of b if b's>c's

else

>>number of a=number of c

>>if c's>b's

>>we cannot decide which is bigger in between no of b's and no of c's, along with a in pushdown automata.

>>so it is not CFL..

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.