Author |
Topic: pushdown automata and context free language (Read 5475 times) |
|
jop
Newbie
Posts: 1
|
 |
pushdown automata and context free language
« on: Feb 10th, 2013, 3:07pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
 |
Re: pushdown automata and context free language
« Reply #1 on: Feb 11th, 2013, 2:20am » |
Quote Modify
|
Define PDA and CFG.
PS: CFG would be Context-Free Grammar.
Oops, silly me! It's in the title.
|
| « Last Edit: Feb 11th, 2013, 9:50am by Grimbal » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: pushdown automata and context free language
« Reply #2 on: Feb 11th, 2013, 9:02am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: pushdown automata and context free language
« Reply #3 on: Feb 11th, 2013, 11:21am » |
Quote Modify
|
on Feb 11th, 2013, 9:02am, 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
|
|
IP Logged |
--SMQ
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print