Stack Overflow
Stack Overflow

Questions tagged [pushdown-automaton]

A pushdown automaton (PDA) is a finite-state automaton with added stack based memory. It is a mathematical description of an algorithm for parsing context-free languages.

PDAs extend finite automata via a stack-based memory, and transitions can push/pop symbols to/from the stack. Deterministic PDAs (ones for which there exists only one legal transition at any time) are strictly weaker than non-deterministic ones; such is not the case for finite automata (PDAs are more powerful) or Turing machines (PDAs are weaker).

186 questions
11
votes
4 answers

Checking if a string consists of balanced parenthesis

I wrote the following program to check strings for balanced parenthesis: isBalanced xs = isBalanced' xs [] isBalanced' [] [] = True isBalanced' [] _ = False isBalanced' ('(':xs) ys = isBalanced' xs (')':ys) isBalanced' ('[':xs) ys = isBalanced'…
fredoverflow
  • 256,549
  • 94
  • 388
  • 662
8
votes
2 answers

How can I have a constrained Finite State Machine in Haskell / Idris?

EDIT: Users @apocalisp and @BenjaminHodgson left awesome answers below, skip reading most of the question and jump to their answers. TLDR of the Question: How can I go from the first picture, where FSM states combinatorial explode, to the second…
Josh.F
  • 3,666
  • 2
  • 27
  • 37
6
votes
5 answers

Design a PDA of all strings of 0's and 1's so that the number of 1's is twice the number of 0's

While practicing for my final exams I found this question in Automata Theory, Language and Computation by J. Hopcroft, R. Motwani, J. Ullman on page 222. PDA should accept string in which the count of number of 1's is twice of number of 0's and if…
user3276435
  • 265
  • 1
  • 3
  • 13
6
votes
1 answer

confusion in finding first and follow in left recursive grammar

Recently I faced the problem for finding first and follow S->cAd A->Ab|a Here I am confused with first of A which one is correct {a} , {empty,a} as there is left recursion in A's production . I am confused whether to include empty string in…
rajkumar
  • 365
  • 5
  • 10
6
votes
2 answers

Is there a programming language that only has the power of a deterministic push-down automata, and no more?

Some programming problems don't require the full power of a Turing machine to solve. They can be solved with much less power. I am seeking a programming language with lesser power. Does there exist a high-level programming language that is…
Roger Costello
  • 3,007
  • 1
  • 22
  • 43
5
votes
1 answer

Pushing/popping stack in reverse order in a Pushdown Automaton

So I'm studying for a test I have coming up on pushdown automata and context-free languages and I'm stuck on this one construction. I have every part of this automaton completely working perfectly except for one part which I will explain below. The…
JayB
  • 397
  • 6
  • 21
5
votes
1 answer

Is the language {0^n 1^n 0^k | k != n} context free?

I believe this language isn't context free, because there is no chance that a PDA could compare 2 blocks of 0's and 1's of the same length and also remember it's length for later use. Unfortunately, I have no idea how to prove it. I tried using the…
Robert777
  • 801
  • 3
  • 12
  • 24
5
votes
2 answers

How to design a pushdown automata

How would i design a PDA that accepts balanced parenthesis and brackets for instance ([][]), I am having a hard time getting started. I need help writing transition functions for this problem. Any help is appreciated
Israel Rodriguez
  • 209
  • 2
  • 8
  • 15
4
votes
5 answers

PDA to accept a language of strings containing more a's than b's

Produce a PDA to recognise the following language : the language of strings containing more a's than b's I have been struggling with this question for several days now, I seem to have hit a complete mental block. Would any one be able to provide…
user1301430
  • 189
  • 1
  • 2
  • 11
4
votes
1 answer

What type of languages are accepted by a PDA in which stack size is limited?

What type(s) of languages are accepted by a PDA in which stack size is limited to, say 20 items? In my view it should still be CFL, because there is a temporary memory to store.
Prashant Bhardwaj
  • 1,203
  • 2
  • 18
  • 26
4
votes
3 answers

What language does this Pushdown Automata (PDA) accept?

Exam tomorrow and the prof let us know a question that would be on it :). In the context of this diagram, L is epsilon (The empty string), and Z0 is the stack empty symbol. I've made some progress in determining a few rules about the words the…
DJSunny
  • 1,970
  • 3
  • 19
  • 27
4
votes
1 answer

Matching groups of nested parentheses using Regex and Pushdown-Automata

I'm working on a c# regular expression that can match nested constructions (parentheses in this case) as well as arbitrary operators (a '|' character in this case). I've gotten started by using a push-down automata as described here. What I have so…
Tim Capps
  • 76
  • 7
3
votes
2 answers

PDA for {a^n b^m | n<=m<=2n}

Can someone help me design PDA for {a^n b^m | n<=m<=2n}. Can you please design one with explanation.
RJ Naskar
  • 31
  • 1
  • 2
3
votes
2 answers

Pushdown Automata in Haskell using the List Monad

I'm trying to implement Pushdown Automata (as described in Sipser's Introduction to the Theory of Computation) in Haskell. I have a working definition: import Data.List import Data.Maybe(fromMaybe) -- A Pushdown Automaton with states of type q, --…
tolUene
  • 572
  • 3
  • 18
3
votes
1 answer

accepting/rejecting Pushdown automata in haskell

I am trying to create a Pushdown Automata checking in Haskell. Basically, a function which takes (start_state, final_state, set_of_rules) and a string. It should return Accepted if the string is accepted by this PDA and Rejected otherwise. This is…
Roman Procházka Jr.
  • 131
  • 4
  • 14
1
2 3
…
12 13