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

learn more… | top users | synonyms

1
vote
1answer
82 views

Calculi for a computability class

Proving two push down automata equivalent is undecidable. But proving two finite state machines equivalent is decidable. You also cannot write a programming language that allows expressing the ...
1
vote
2answers
28 views

Techniques to create a PDA for a language that is the conjunction of two languages

When I was working with finite automata, I figured out that we can put together two FA two build a new one that is the intersection between the two. This is possible because regular languages are ...
0
votes
1answer
62 views

DPDA for $L_1 = \{0^i1^j2^k3^m | i,j,k\ge 0,m = i+j+k\}$ according to empty stack criterion

I'm having some trouble with the following language: $L_1 = \{0^i1^j2^k3^m | i,j,k\ge 0,m = i+j+k\}$ with alphabet $A=\{0,1,2,3\}$ I'd like to find a deterministic pushdown automata to recognise it ...
0
votes
2answers
70 views

How to convert PDA to CLF

I learned how to convert context-free grammar to pushdown automata but how can I do the opposite? to convert PDA to CFG? For example: to write CLF for the automata EDIT: My attempt: $S=A_{03}$ ...
2
votes
0answers
22 views

Why we don't care about minimizing Push Down Automata & Turing Machines? [duplicate]

I never heard or read about the concepts of "Minimizing Push Down Automata or Turing Machines"? why we are not concerned about minimizing them, in general?
2
votes
1answer
47 views

Why is this NPDA?

I am studying PDA at the moment, and I came up with this question. The figure above tells me that although both PDA accept the same language, one is non-deterministic and the other is ...
0
votes
0answers
13 views

PDA for recognize two same substrings in string [duplicate]

Good day, I have to devise a push-down automata for this language L={w∈{a,b}∗, w is not of the form xx for any x∈{a,b}∗} It's not necessary to write down ...
-1
votes
1answer
60 views

Is a Pushdown Automata possible for this language?

PDA for a Language L = { $a^i b^j \mid i \neq 2j+1 \}$ over the Alphabet $\Sigma = \{a,b\}$ If it can be constructed, how? Edit : I've tried make the PDA for $$L = \{ a^i b^j \mid i = 2j+1 \}$$ ...
0
votes
0answers
36 views

confirmation of pushdown automata questions

I have the following questions below that I have gotten from a practice paper but have no answers for them. I have completed them but am not sure if they are right, If anyone could confirm whether ...
-1
votes
1answer
46 views

How to find what language a PDA accepts?

Given the following PDA describe the language it accepts. ...
1
vote
0answers
44 views

What are some applications of 2 stack pushdown automata?

What are some real world application for 2 stack pushdown automata, as i can only find pushdown automata applications in the internet
0
votes
2answers
55 views

Can a deterministic language be accepted by a deterministic Push Down Automaton?

I have a question that asks me to show that the PDA of the language L is not deterministic, but that the language is nevertheless deterministic. I was under the assumption that any deterministic ...
2
votes
0answers
38 views

Expressing classic automata in modern terms

This semester I was introduced to finite automata (FSM), then pushdown automata (PDA), and now the Turing machine (TM). Granted that there're many possible implementations of these abstractions ...
1
vote
0answers
50 views

what is the CFG for a^ib^jc^k where i+2j=3k [closed]

i'm trying to find a context-free grammar that recognize the language below: $L=\{a^ib^jc^k| i+2j=3k\}$ i was trying to divide this language to three languages like this: $ i=j=k$ $ 3i=k \text{ ...
1
vote
0answers
30 views

Language involving length constraints and reversal

Why is the language $A=\{wtw^r: w,t\in\{0,1\}^*\text{ and }|w|=|t|\}$ not a context free language? It is turning out to be really tricky. Is there an easy way to show this?
-4
votes
1answer
54 views

How to design a PDA for the language of words with s a's, t b's and s⋅t c's? [closed]

I have the language $\qquad L=\{ a^s b^t c^m \mid s,t,m \; \in \; \mathbb{N^{+}} \text{ and } t<4, s \cdot t=m\}$. How do I go about designing a PDA for it ? I can't figure out a way to deal ...
1
vote
2answers
95 views

Formal construction of PDA intersecting a DFA

Given the PDA $P = (Q_P,\Sigma,\Gamma_P,\delta_P,F_P)$ and the DFA $D = (Q_D, \Sigma, \delta_D,q_D,F_D)$ What is the 6-tuple definition of the PDA such that: $L(P') = L(P) \cap L(D)$ I don't ...
7
votes
1answer
262 views

Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?

Let a input string be given as $w_1w_2...w_n$. Then if a NFA is currently in state $r$ ( and has read the input upto alphabet $w_i$ ) then before reading the next input symbol the NFA splits into two ...
2
votes
1answer
50 views

When does a PDA split?

In case of NFA, if the NFA is in a state and reads $\epsilon$ ( empty string ) the NFA splits in to two, with one being at the current state and other with the state along the $\epsilon$ transition. ...
3
votes
1answer
50 views

How powerful is a k-stack pushdown automaton with a unary stack alphabet?

I'm interested in pushdown automata with a unary stack alphabet: let's call them UPDA's. Define a $k$-UPDA to be a pushdown automaton with $k$ stacks, each with a unary stack alphabet. I've figured ...
1
vote
1answer
170 views

Construct Pushdown Automaton that accepts language $x\in\{a,b\}^*, a=2b$

I've been studying Computation Theory, and in an exercise I am asked to construct a PDA that accepts the language $L=\{x\in(a,b), \#_a(x) = 2\#_b(x)\}$, where $x$ is the input string and ...
0
votes
0answers
51 views

Linear time parsing from star of context free language

I was wondering if there are cases in which the star closure of a language can make the resulting language easier to parse. In particular, if I have this grammar: ...
1
vote
1answer
262 views

Converting final state PDA to empty stack PDA

I'm having a problem understanding this conversion. Let's say we have a CFL like this: $ { a^nb^m : n > m } $ A final state acceptance PDA for this language would push $A$ symbols in the stack for ...
4
votes
1answer
178 views

pda: transformation between acceptance by empty stack and final states

I am stuck with understanding the transformation of final-state acceptance automaton into empty-stack acceptance automaton. From everywhere that I've read, it always says introduce a new start state ...
0
votes
2answers
44 views

Push down automata what to do when there is no suitable transition

This is a question that has emerged from a recent quiz I have taken. In short Consider the following transitions on a push down automaton. Assume the starting state is q. Which one of the ...
0
votes
0answers
11 views

Construction of NPDA with inequality check [duplicate]

I'm currently struggling to construct a nondeterministic PDA with an amount of states in $O(n)$ that accepts the following language: $L = \{wcx \, | \, w,x \in \{a,b\}^n \land w \not= x\}$ with c ...
3
votes
1answer
41 views

Proof that CFL aren't closed under intersection using synchronous parallel (N)PDA composition

It is well known that the class of CFLs is not closed under intersection as follows e.g. from the following example: $$L_1 \cap L_2 = \left\{ a^mb^mc^n \mid m,n \ge 1 \right\} \cap \left\{ a^mb^nc^n ...
2
votes
0answers
37 views

NPDA, guessing capability and stack as an exclusive resource

Context Free languages is exactly the class of languages recognized by Nondeterministic Push Down Automata (NPDA). We can view a nondeterministic transition as a guess; for example if $L = \{x x^R ...
-1
votes
1answer
122 views

Context free grammar $\{a^n b^m c^k\; : \;k>m \; \; k>n\}$

Is this a CFL? $$\{a^n b^m c^k\; : \;k>m \; \; k>n\}$$ When on seeing $a$'s and $b$'s I push them onto stack and as I see $ c$ as input if $ TOS$ is $b$ ,I pop them ,again if $TOS$ is a,I pop ...
0
votes
0answers
12 views

Determine whether the following languages are context free [duplicate]

$L$ is context free and $L_r$ is regular and $A$ is an alphabet. The languages are: $$ L_1 = \{ uv ; u \in L , v \in L^R , |u| = |v| \} $$ $$ L_2 = \{ uxv ; uv \in L_r , x \in A, |u| = |v| \} $$ ...
1
vote
1answer
39 views

When to pump up and down?

When I'm solving a question I usually spent too much time testing whether I should pump or down? Is there any formula to know when to use which? Also, on proofing non context free grammar we use ...
0
votes
2answers
170 views

Find a pushdown automaton for { x#y ∣ x ≠ y }

I was told to built a PDA that recognizes the following language: $$L = \{x\#y \mid x,y \in \{0,1\}^{\ast} \wedge x \neq y\}$$ My attempt is basically to push $x$ to the stack for every $1$ and $0$ ...
1
vote
1answer
52 views

How to create this pushdown transducer? (formal languages and automata)

Create a pushdown transducer that translates $a^m b^{2m}c^{m+n}$ into $b^{n-m}$, with $n\geq m \geq 0$. How should I use the stack to remember or to compute how many characters of c to read? And how ...
1
vote
1answer
165 views

How exactly does a two stack pushdown automaton work?

I have to explain how a 2-PDA works and then write a program (in Delphi) which simulates a 2-PDA step by step for the language $L = \{w\$w\ |\ w ∈ \{0,1\}^n\ with\ n>0\}$. So far, so good. Now I ...
2
votes
1answer
31 views

What additional expressivity does polyvariance give in pushdown CFA?

I'm reading through Pushdown Control-Flow Analysis of Higher-Order Programs, which presents a synthesis of the Abstracting Abstract Machines technique and pushdown automata to get static analysis ...
11
votes
1answer
392 views

Is it decidable whether a pushdown automata recognizes a given regular language?

The problem whether two pushdown automata recognize the same language is undecidable. The problem whether a pushdown automata recognizes the empty language is decidable, hence it is also decidable ...
2
votes
2answers
143 views

When do we need to change the state of a push down automata? [closed]

I'm new to the subject of automata theory. I get most of the stuff, but I cannot figure out when to change the state of the machine, and when to keep the state unchanged for a particular transition ...
1
vote
0answers
21 views

Are deterministic context-free languages closed under reversal of languages? [duplicate]

It is well known that context-free languages are closed under the reversal of $L$. My answer to the question "Is the time reversal symmetry of non-deterministic computations important?" notices that ...
1
vote
0answers
35 views

Is $\{u\#v \mid u\not=v\}$ context-free? [duplicate]

Is the following language context-free? $$ \{u\#v\in\Sigma^* \mid u\not=v \text{ and } u,v\in\{0,1\}^*\} $$ You can assume $\{0,1,\#\}\subseteq\Sigma$. Unnecessary background information: I am ...
3
votes
1answer
118 views

Why is $\{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ an inherently ambiguous language?

I came across a very hard interview question in last month’s Ph.D. entrance exam. It was asking which one of the languages is inherently ambiguous. Short answer says 2). Why is the language in 2) an ...
1
vote
1answer
74 views

Construction of a counter automaton for the complement of the palindromes

How would I go about constructing a nondeterministic 1-counter automaton for the language $L$ that is the complement of the palindromes $\overline{L}=\{ww^{rev}\}$ over a 2 symbol alphabet $\Sigma = ...
0
votes
1answer
250 views

PDA with N-Stacks comparison with Turing Machines [duplicate]

Is it possible to compare PDA having N-Stacks with Turning Machines. Are they equally powerful in this situation? It's been told that PDA with 2-Stacks is equally powerful to Turning Machine. But ...
1
vote
1answer
68 views

Is a k counter automata a special kind of PDA?

I understand that a 1 counter automata is a special kind of PDA where the stack alphabet consists of one symbol (ignoring the fixed bottom symbol) but what about 2 counter automata? Is it a special ...
0
votes
1answer
61 views

Simple question: Pushdown automata transition

I am currently constructing pushdown automata. can I push/pop alphabet more than two in a transition?? For example, $\delta$(a, a/aaa) means, in the state of input alphabet 'a' and stack point 'a' ...
3
votes
2answers
119 views

Can we build a nondeterministic decider PDA using two PDAs accepting a language and its complement?

When talking about turing machines, it can be easily shown that starting from two machines accepting $L$ and its complement $L^c$, one can build a machine which can fully decide if a word is inside ...
4
votes
2answers
400 views

Which class of languages is accepted by PDA when we restrict the stack to logarithmic size?

Let $\mathrm{LOG}_{\mathrm{CF}}$ be the class of all languages recognized by a Pushdown-automaton that uses $\leq \log n$ cells of its stack for each input of length $n$. Obviously, this class is a ...
5
votes
5answers
222 views

is it possible to minimize pushdown automata?

is it possible to minimize pushdown automata? If no, why? Is it because for minimization the equivalence classes need to have a finite index and we cannot guarantee that for CFG?
0
votes
1answer
294 views

Create cfg and npda/pda for Language {ww}

I've been trying to make a CFG, and npda/pda for this language (to construct an npda for accepting the language): L(M)={ww:w∈{a,b}∗,|w| is even}. i had already solved the reverse of the language ...
-1
votes
1answer
167 views

Create CFG and pushdown automaton for {ww} [duplicate]

I've been trying to make a CFG, a pushdown automaton and a regular expression for the language $\qquad L(M) = \{ww : w \in \{a, b\}^*, |w| \text{ is even}\}$. I understand how the reverse of the ...
-1
votes
2answers
235 views

Pushdown Automata: CFG to PDA

I have the following grammar for a context-free language: $G = (\{S,A,B\}, \{x,y,z\}, P, S)$ with $P = \{S \rightarrow A, A \rightarrow xAz, A \rightarrow xBz, B \rightarrow y\}$ My question is: How ...