wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> pushdown automata and context free language
        
(Message started by: jop on Feb 10^th, 2013, 3:07pm)

Title: pushdown automata and context free language
Post by jop on Feb 10^th, 2013, 3:07pm

for a set of strings with the pattern:
10, 10100, 101001000, 10100100010000........

(the number of consecutive zeros equals n if they are trailing the nth "1" in the string)

Is there a PDA or CFG for this? If not, is there a PDA or CFG for the set of strings that don't conform to this pattern?

Title: Re: pushdown automata and context free language
Post by Grimbal on Feb 11^th, 2013, 2:20am

Define PDA and CFG.

PS: CFG would be Context-Free Grammar.

Oops, silly me! It's in the title.

Title: Re: pushdown automata and context free language
Post by towr on Feb 11^th, 2013, 9:02am

It's been a while since I've dealt with grammar and automatons; can a PDA (pushdown automaton) have two stacks? Because with two stacks I can easily see it done.

Title: Re: pushdown automata and context free language
Post by SMQ on Feb 11^th, 2013, 11:21am

on 02/11/13 at 09:02:46, towr wrote:

It's been a while since I've dealt with grammar and automatons; can a PDA (pushdown automaton) have two stacks? Because with two stacks I can easily see it done.

No. Two stacks are equivalent to an infinite tape and now you have a Turing Machine rather than a PDA.

--SMQ