Questions tagged [pushdown-automata]

Questions about state machines with a single stack for memory. They characterize the class of context-free languages.

Filter by
Sorted by
Tagged with
0
votes
1answer
342 views

How do I normalize a push down automaton?

Looking at the above PDA, I am unsure whether or not it is normalized. Specifically, the loop transition from $q_1$ to $q_1$, because I know a transition must either push OR pop from the stack. Does ...
2
votes
1answer
519 views

A PDA to recognize the Intersection of two regular languages?

I am studying pushdown automata and I am working on a problem that asks to generate a PDA that accepts the following regular languages: Intersection of L1 and L2 L1 = L (aaa* bab) L2 = L (aab* aba)...
1
vote
2answers
192 views

Upper bound for the union of $n$ DFAs of size at most $m$?

Let $\Sigma$ be an alphabet of size $2$, and let's consider $n$ regular languages $L_i \subseteq \Sigma^*$ respectively recognized by $n$ minimal DFAs $D_i$ whose size are bounded by $m$. As the ...
0
votes
1answer
199 views

Push-down Automata Construction

Construct a push-down automata to recognize the language $ A = \{u\#v \in \{0,1,\#\}^{*} | u = v^{\complement} \} $. Here, $v^{\complement}$ is the bit-complement of v. I don't see how to perform ...
0
votes
1answer
326 views

Determining whether $ L = \{ 0^n1^{n^2} | n \ge 0 \} $ is a CFL

Assuming $L$ is defined as follows: $$ L = \{ 0^n1^{n^2} | n \ge 0 \} $$ I'm trying to either prove/disprove whether $L$ is CFL or not. My intuition tells me its not CFL since I cannot express the ...
0
votes
0answers
327 views

Constructing a minimal pushdown automaton for counting characters in substrings

I have to construct a pushdown automaton for the following language over alphabet {a,b,c}: L={ ucv | |u|!=|v|; u,v={a,b}* } (note: u,v are substrings over alphabet {a,b}, |u| is length of substring ...
1
vote
1answer
43 views

Is a String with no parantheses considered having balanced parantheses?

Say I have a language over the alphabet {x,y,(,)} . The language's rules are: any string over that alphabet with balanced parentheses. Clearly x(), (xy) , ()()xxx, ((xx)) are accepted. BUT My ...
0
votes
2answers
451 views

Push down automaton for Language of same number of as and bs

The task Find a pushdown automaton $M$, so that $L(M)=\{w \in \{a,b\}^*\ |\ |w|_a=|w|_b\}$, where $|w|_a$ denotes the number of $a$s in a word $w$. My solution I'm using the Wikipedia notation. $$...
4
votes
1answer
269 views

Simulate NPDAs with DTMs using only polynomial overhead

We know by polynomial-time parsing algorithms like the classical CYK algorithm that $\mathrm{CFL} \subseteq \mathrm{P}$. Furthermore, it is easy to show by direct simulation that $\mathrm{DCFL} \...
0
votes
0answers
108 views

Why is DCFL not closed under kleene star? [duplicate]

I honestly haven't an idea how to proof that eventhough I can understand the background, could someone help me?
1
vote
0answers
376 views

Create PDA for the alphabet {a,b} starting and ending with the same symbol [duplicate]

I have to design PDA accepting language: set of strings over ∑ {a, b} starting and ending with the same symbol. From that moment i think good way is to remember only first element because the last one ...
3
votes
1answer
341 views

Equivalent DPDA that always halts for every DPDA with empty stack language

I want to show that for every deterministic pushdown automaton with the language of the empty stack there is a deterministic pushdown automaton that always halts. my transition function of $P$ is $\...
0
votes
1answer
47 views

What can be said about the given language?

$L = \left \{ ab^{n}a^{n}|n>0 \right \} \bigcup \left \{ aab^ka^{2k} | k>0 \right \}$ What can be said about the given language L ? According to me, I think it is CFL and not DCFL as I tried ...
3
votes
2answers
1k views

When does a PDA halt?

In DFA/NFA the automaton halts when it finishes reading the string. In a PDA there's the string and the stack. When the string is finished and there are symbols on the stack does it ignore them? Or ...
0
votes
0answers
68 views

How can I build this automaton?

The automaton has to recognize the language $(a^n)(b^m)$ so the number of $b$s is at least the number of $a$s and at most twice that number. The only thing I have achieved is to get an automaton that ...
2
votes
1answer
486 views

Algorithm to detect if word belongs to pushdown automaton

I am creating a simple program to detect if the given pushdown automaton accepts the given word, and I have a problem in finding an algorithm that does that. My thought at first would be to go ...
1
vote
1answer
259 views

How to represent a double push or double pop operation in push down automata

I want to know the theoretical representation of a double push or a double pop in pda
0
votes
1answer
3k views

Push down automata acceptance by Empty stack and final state

I have a very basic question. Can we have a PDA which can accept a string by both final states and empty stack? Can the same PDA accept by the two modes simultaneously ? If there are final states ...
3
votes
1answer
1k views

PDA for { xy : |x| = |y|, x ≠ y} from its grammar, and intuition behind it

I know the grammar for the language $\{ xy : |x| = |y|, x ≠ y \}$ if $\Sigma=\{a,b\}$: $$ \begin{align*} &S→AB∣BA \\ &A→a∣aAa∣aAb∣bAa∣bAb \\ &B→b∣aBa∣aBb∣bBa∣bBb \end{align*} $$ I ...
1
vote
1answer
85 views

How do you read this context-free language?

say you want to make a Pushdown Automaton to recognize this language. What exactly does the +1 mean? I see in the example it just pushes an a to the stack before arriving at an acceptance state but I ...
0
votes
2answers
78 views

Context free grammar issue at pda

I'm studying for my computing languages and I have some problem on getting the production rules from a push down automata. The automaton accepts all strings over alphabet $\{e,k,q,y\}$ of the form $w\...
2
votes
1answer
715 views

PDA and CFG of language of regular expressions

I am stuck on a problem involving PDA's and CFG's. The problem is as stated: Give a CFG and a PDA for the language of regular expressions over the alphabet $\{a, b, c\}$. Give the formal tuple ...
1
vote
0answers
26 views

almost realtime push down relation vs realtime pushdown relation?

Almost realtime pushdown relation pop a symbol for each empty step. Realtime pushdown relation does not perform any empty step. What do they mean by empty step?
0
votes
0answers
100 views

Reduce Nondeterminism in Pushdown Automata

I know there might be some situations where we want transitions to be only taken when the stack is empty, and transitions to be taken only when the input stream is empty. We can create an additional ...
2
votes
1answer
97 views

Is $L / R$ context free?

I was reviewing the post If $L$ is context-free and $R$ is regular, then $L / R$ is context-free? I completely understand why $L/R$ is context free. I just tried a different approach, which is not ...
2
votes
1answer
161 views

PDA with an unusual double inequality

I have an odd PDA problem that I cant seem to construct. I haven't come across one like this before. $L = \{w\in\{a,b\}^{*} : 3\#_{a}(w) \leq 5\#_{b}(w) \leq 4\#_{a}(w)\}$ Could I get some pointers ...
-2
votes
2answers
1k views

If accepted by dpda and npda,then it is regular. Is it correct?

If accepted by dpda and npda,then it is regular. Is it correct?.I had confusion that some where I studied that a regular language is exactly should accepted by finite automata.....
4
votes
1answer
313 views

Proof that PDA's with different definitions have same expressive power

Let $P$ be a push down automaton $(Q,\Sigma,\Gamma,\delta,q_s,F)$, where $Q$ is the set of states, $\Sigma$ is the input alphabet $\Gamma$ is the stack alphabet $\delta$ is the transition function ...
4
votes
1answer
386 views

Parsing CFLs (simulating PDA vs CYK algorithm)

We can simulate the PDA and parse the language with the following operations (vaguely): Read the input symbol and top of stack - $O(1)$ Check all the transition rules (must check all for non-...
0
votes
0answers
423 views

Converting a CFG with epsilons into a DPDA

I have a CFG: S -> $T$ T -> T+T|T-T|T/T|(T)|CX|I X -> XX |C|N|_|@ C -> a|b|c|....|z|A|B|C|...|Z|_ N -> 0|1|2|....|9 I -> NI|N Here @ means epsilon. The above is a valid arithmetic expression ...
2
votes
1answer
2k views

Why can you push multiple symbols on a PDA stack at once?

I'm really new to learning about PDA's and stuff, i understand that on a edge between 2 nodes you'll have something like this a,b->c. This means: if a is in the beginning of your string and b is on ...
5
votes
1answer
778 views

Why can PDAs only write one symbol to the stack according to this definition?

This is in regards to the definition 2.13 of non-deterministic PDA given in Theory of Computation 3rd ed. by Michael Sipser. The transition is defined as $$ \delta: Q\times \Sigma_\varepsilon \times ...
0
votes
1answer
181 views

I can't understand this example of PDA Automata

looking for old tests of Language Theory, I see this exercise: Give a PDA automata that recognize the language $L = \{w \in \{a,b\}^*,\ 2|w|_a=3|w|_b\}$ They propose this solution: Can anyone help ...
0
votes
0answers
16 views

What is the pushdown automata for the language {0, 1}* Where |0| = 2 * |1| or |1| = 2 * |0|? [duplicate]

Having a lot of trouble figuring this out. It seems to me to be impossible. I could do one side of the OR - but the fact that the string can begin with 100 1's and then have 200 b's seems like it can'...
4
votes
1answer
3k views

Union of a Deterministic Context-free language and a Regular Language is a Deterministic Context-free Language

In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic ...
2
votes
1answer
379 views

Is a PDA's stack size linear bounded in input size?

I was thinking as follows: At each step, a PDA can put arbitrary many symbols onto the stack. But this number is constant for every individual PDA, so it can't be more than, say, $k$ symbols per step. ...
2
votes
1answer
67 views

Prove that language of possible stack content is regular

So, here's the problem: Suppose that $A=(Q,\Sigma,\Gamma,\delta,s,\bot, F)$ is a PDA, let $$L = \{ \gamma \in \Gamma^* \hspace{5pt}|\hspace{5pt} \exists_{x,y\in \Sigma^*} \exists_{q\in Q}: (s,x,\bot)...
0
votes
2answers
1k views

Proof for TM accepting any PDA-language

How do you suggest I go about proving this: Give a short, basic outline of a proof that Turing machines can accept all languages accepted by PDAs. You are allowed to use a non-standard Turing machine....
0
votes
1answer
379 views

Showing a language is context free. Use PDA or CFG?

I am wondering on how to approach a specific problem I am struggling with. I am not understanding which way to approach it and how to solve it. Show language $L$ is context free, where $L = \{\text{...
1
vote
1answer
1k views

Determine whether a context-free language is deterministic or not

I define language $L = \{a^k a^m b^m c^k \} \cup \{a^n b^n b^k c^k\}$ and I want to determine if it's deterministic context free language or it is nondeterministic. so I tried to create pushdown ...
3
votes
2answers
338 views

How to understand pushdown automata intuitively?

What is an intuitive way of understanding what a push down automaton is capable of computing?
1
vote
1answer
3k views

PDA for all non-palindromic strings of even length

I had a homework assignment where I had to build a PDA over the alphabet $\{a,b\}^*$, accepting $L = \{x \mid x \text{ is even but not a palindrome}\}$. I already turned it in, but I know I had it ...
6
votes
1answer
752 views

Removing $\epsilon$ transitions in a NPDA

NPDA's and general NFA's may not halt for finite inputs like DFA's do because of their $\epsilon$ transitions. However, NFA's with $\epsilon$ transitions could be converted to those without any $\...
1
vote
0answers
61 views

Decidability Proof of $A_{Cfg}$

I am a beginner to complexity theory and I came up with the following proof of decidability of $A_{Cfg}$ = {$<G,w>|G$ is a context free grammar that generates string $w$} The Turing machine ...
1
vote
0answers
64 views

turing machine decidability language

I must show that this language is decidable but I think it's not {D, Ρ} | D is a DFA and P is a ΡDA which L(D) ∩ L(Ρ) = ∅ } Here what I think I give a reduction from E(TM). I suppose that this ...
1
vote
1answer
1k views

Why do we pop the dollar symbol when it's already present in the stack in PDA?

Could anyone tell the reason for popping the top of stack(dollar symbol) as said in this lecture(p.54) when there's already dollar symbol in the stack. I would like to know if we could replace the ...
0
votes
1answer
96 views

Characterizing a CFG equivalent to a special type of PDA

Consider a nondeterministic PDA $P$ which pushes/pops at most one stack symbol on a transition. Suppose that for every string $\sigma \in L(P)$, there is an accept computation of $\sigma$ in $P$ which ...
0
votes
1answer
85 views

Pushdown Automata: How can I recognize a ratio threshold between two symbols in a string?

I'm trying to design a pushdown automata where there are two symbols in the alphabet and the accept state is when there is >= 60% of symbol A. I'm trying to think in terms of what to save on the ...
-1
votes
1answer
706 views

Converting a language to a PDA?

I am trying to convert the follow language $$L = \{0^m1^n \ | \ 0 \le m \le n \le 2m\}$$ We have an exam in 2 days and the professor didn't teach us much about PDA's. They will be on the test though ...
0
votes
1answer
97 views

Relation of deterministic push down automata and lower elementary recursion

Deterministic context free languages are the context free languages that can be accepted by a deterministic push down automata. Deterministic context free languages can be recognized by a ...

1 4 5 6 7 8