Skip to main content

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
6 votes
1 answer
279 views

Are Context-Free languages closed under XOR?

First, let's generalize the notion of XOR on strings over the ${0,1}$ alphabet. For strings of the same length, the XOR is the bitwise XOR. For strings of different lengths, we define $ \text{xor}(w, \...
Toobatf's user avatar
  • 61
-1 votes
1 answer
25 views

Create a cfg for the language L = {w ∈ {a,b,c}* : |w| = 3na(w)}

All I know about this language is that it is equivalent to the following: $$L = \{w \in \{a,b,c\}^{∗} : n_b(w) + n_c(w) = 2 * n_a(w)\}$$ but I have absolutely no idea how to create a CFG for it.
AmirMohammad Shakeri's user avatar
2 votes
1 answer
36 views

PDA for Palindrome Strings

I am studying Automaton Theory for first time and I am having problems to see if I do well some exercises and if I really finish them. For example, one exercises asks to give a PDA for all palindrome ...
Daniel García's user avatar
0 votes
1 answer
30 views

PDA for $\{a^i b^j c^k : i \neq j \}$

I am trying to write a PDA for $L := \{ a^i b^j c^k : i, j \in \Bbb{N} \land i \neq j \}$, but I am getting stuck since I am new with Automaton Theory. My idea was to make PDAs for both $\{ a^i b^j c^...
Superdivinidad's user avatar
-1 votes
1 answer
30 views

Construct an NPDA for the language where the number of a's <= 3 times the number of b's

I am trying to construct an NPDA for $L = \{\omega \in \{a,b\}^* | n_a(\omega) \le 3 \times n_b(\omega)\}$. This means that for every $b$ there can be at most $3$ $a$'s So far, I understand that for ...
William's user avatar
2 votes
2 answers
45 views

Termination of standard encoding of CFG as PDA for words not in the language

The construction of a PDA from a CFG on wikipedia (1) is like a nice exercise for implementing a minimal-and-slow-but-functional parsing algorithm. I have a question about termination of the PDA that ...
bobismijnnaam's user avatar
0 votes
1 answer
58 views

Is the language L = {a^m b^n a^n b^m | m, n >= 1} context free?

Based on my understanding, I ended up at the following grammar: A -> bAa | λ S -> aSb | A | λ Is it sufficient to say the above language L = {a^m b^n a^n b^m ...
Kilaru Vasudeva's user avatar
1 vote
1 answer
92 views

problem understanding proof about deterministic pushdown automaton

I'm having problem understanding the first part of this proof. I don't understand why it needs to hang at $(p,\epsilon,\epsilon)$ why can't the automaton just keep going, just reading the rest of the ...
lazyelekid's user avatar
0 votes
1 answer
22 views

Can I maintain Determinism of PDA just by changing stack symbol while keeping state and input symbol same?

for a transition $\delta(q,\sigma,X)$, if I keep state $q$ and input symbol $\sigma$ same but read different stack symbols in place of $X$ will it still be called deterministic PDA because as per my ...
hxdshell's user avatar
0 votes
0 answers
35 views

Write a PDA that accepts the language of strings over {a, b, c} where the number of instances of ab is equal to the number of instances of bc

As the question is stated above, these are the list of transition functions I currently have: $alphabet: {a, b, c}$ $start: q0$ $accepting: {q3}$ // Initialization $q0 ($ _, _ $\rightarrow$ \$, $q1)$ /...
Luke Jones's user avatar
-1 votes
2 answers
45 views

Pushdown Automaton accept all words belong to language over (a,b) where the first letter 'a' has half of the occurences of the second letter 'b'

Pushdown Automaton accept all words belong to language over (a,b) where the first letter 'a' has half of the occurences of the second letter 'b'. Can someone help me with a JFLAP like digram of this ...
Vunag's user avatar
  • 1
0 votes
1 answer
51 views

A context-sensite grammar for the language of sequences of two different types of parentheses with possible intersections?

Consider the language $L$ over the alphabet (,[,),] such that any word $w \in L$ if formed as a shuffle of two (possible empty) well-formed sequence of parenthesis: one over (,) and another over [,]. ...
kerzol's user avatar
  • 103
1 vote
0 answers
36 views

Efficiently generating valid strings from a deterministic CFG, one symbol at a time, subject to a length limit

Background I'm writing algorithms for generating arbitrary strings from a formal language $L \subseteq \Sigma^*$, one symbol at a time from left to right, while also ensuring that the strings do not ...
Jerry Ding's user avatar
0 votes
0 answers
45 views

PDA equivalent to an $\varepsilon$-free PDA

Say that a PDA is $\varepsilon$-free if it contains no $\varepsilon$ transitions (that is to say, $\varepsilon$ is not in the recognized string symbols even if it still is a stack symbol), but it may ...
Addem's user avatar
  • 367
0 votes
1 answer
16 views

Hardwiring input in DFAs and PDAs

A Turing Machine can be converted into a Turing Machine that has a specific input coded into it's description. This Turing Machine can then be run on empty input. Can we do the same for PDAs or DFAs? ...
Zee's user avatar
  • 243
2 votes
1 answer
694 views

Is there a one-state PDA that recognizes every context free language?

Here, I read this: For all CFL, there is a one-state PDA that recognizes this language. What is the proof/idea behind this claim? CFL: Context Free Languages PDA: Push Down Automaton
whoisit's user avatar
  • 165
1 vote
1 answer
59 views

Not understanding example of a Pushdown Automata

The first example of a (nondeterministic) pushdown automata given in Linz' An Introduction to Formal Languages and Automata is the following: Example 7.2: consider $Q = \{q_0,q_1,q_2,q_3\}$, $\Sigma =...
Sam's user avatar
  • 143
1 vote
0 answers
54 views

infinite loop in PDA

let L be defined as $L = \{0^{2k} | k \in \mathbb{N}\} \subset \{0,1\}^*$. language L can be described by a nondeterministic pushdown automaton P such that there exists at least one input for which P ...
Jacob Martina's user avatar
3 votes
0 answers
40 views

Length of an $\varepsilon$-computation in complete DPDA

I consider a deterministic pushdown automaton. Given that there are some differences between definitions, here is mine: the syntax is given $A = (Q, \Sigma, \Gamma, \Delta, q_0, Z_0, F)$, with $q_0\...
Nathaniel's user avatar
  • 15.8k
0 votes
1 answer
49 views

Is the Given Languages CFL or DCFL?

$L_1$ = {$a^nb^mc^xd^y$|$n=m$ or $x=y$} $L_2$ = {$a^nb^xc^md^y$|$n=m$ or $x=y$} For $L_1$: Push a's Now pop the same number of b's , Given n=m If Stack is empty and x=y=0 accept the Langauge else ...
Vedant Khandelwal's user avatar
-1 votes
1 answer
43 views

Is this correct Context free grammar(CFG) for these two languages?

Question 1: L = { 0^n 1^n | n > 0 } My answer = S -> 0 S 1 | 10 Question 2: L = { 101^n0^2n | n > 0 } My answer = S -> 101 S 00 | 100 Can anyone correct this if there is any issue with ...
Elijah's user avatar
  • 1
0 votes
0 answers
78 views

Two Counter word count language Nondeterministic Pushdown Automata (NPDA) problem actually Context Sensitive unless counters are multiples

Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
John Daniels's user avatar
0 votes
0 answers
3 views

Two Counter word count language npda' problem actually Context Sensitive unless counters are multiples [duplicate]

Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
John Daniels's user avatar
0 votes
0 answers
4 views

Two Counter word count language npda' problem actually Context Sensitive unless counters are multiples [duplicate]

Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
John Daniels's user avatar
-1 votes
1 answer
25 views

CFGs and Pushdown Automata

Is this the CFG for part (a), S -> AxxyxxA A -> Ax|ε If this is the answer then this grammar would accept &...
Don senu's user avatar
0 votes
0 answers
56 views

1 way 2 stack and 2 way 2 stack Pushdown Accepters that accepts $L=\{a^{(n^2)} \mid n \geq 1\}$

Using a 1 way 2 stack, and a 2 way 2 stack PDA, I want to check if the length of an input string is strictly a perfect square number. How can I do this in both approaches?
user164486's user avatar
4 votes
3 answers
1k views

Are 2 independent PDAs equivalent to a turing machine?

I was thinking about the language $a^nb^nc^n$, which is obviously not context free, but if we run it through 2 automata at the same time (the first for $a$ and $b$ and the second for $b$ and $c$ and ...
NeedHelp's user avatar
-2 votes
1 answer
222 views

DPDA for language $L=\{a,b\}^* \setminus a^nb^n \setminus b^na^n$

How to construct DPDA for the following language $L=\{a,b\}^* \setminus a^nb^n \setminus b^na^n $ $L_1 = \{a,b\}^* \setminus a^nb^n =\{a^i b^j \, | \, i>j\}\,\cup\,\{a^i b^j\ \ | \ i<j\}\,\cup\...
cs_student's user avatar
-1 votes
1 answer
648 views

Show that the language $L=\{w|w$ has odd length and the middle symbol is a $0\}$ is Context-Free and construct a PDA that accepts it

Were w is any string composed over the alphabet $\Sigma = \{0,1\}$. For the first part of the exercise I've tried decomposing the problem into three different ones, mainly the first one is for the ...
Lorenzo's user avatar
0 votes
1 answer
45 views

can you read and push different symbols in a DPDA?

I have an easy question about the DPDA. Could you read an input and push a different symbol to the stack. An example would be A transition from q1 to q2 where read input is v pop is epsilon(empty ...
ee ss's user avatar
  • 3
1 vote
1 answer
190 views

Can a pushdown automaton write more than one symbols on to stack on one reading from from input tape?

The formal definition of the pushdown automata according to Mike Sisper's book on theory of computation is as follows: . The transition function however only takes in one symbol from the stack (after ...
Sbavert's user avatar
  • 51
0 votes
0 answers
63 views

Equivalent context free grammar for every pushdown automaton?

Equivalent context free grammar for pushdown automata [edit] This machine does not accept L = {a^(n)b^(n)c^(n) | n > 0} and instead accepts L = {a^(2n+1)b^(2n+1)c^(2n+1)}; also, as a side note ...
Hiefenhoomer's user avatar
1 vote
1 answer
50 views

Simple pushdown automata question

I'm trying to derive the language it represents. However, I'm kind of new to those topics. What happens if input b is gathered once or more than one time at state q without a in the stack? It does not ...
mark's user avatar
  • 67
0 votes
1 answer
92 views

How PDA decide when and which state to transform to?

[1] gives an example for PDA which contains rules of: (p,e,Z,q,Z) (p,e,A,q,A) and says, The third and fourth instructions say that, at any moment the automaton ...
Doerthous's user avatar
  • 103
3 votes
2 answers
2k views

Mike Sipser and Wikipedia seem to disagree on Chomsky's normal form

Here's what Wiki says: And here's what Mike Sipser says in his Introduction to Theory of Computation: The problem arises when you try to read the two definitions - Mike Sipser seems to be suggesting ...
Sbavert's user avatar
  • 51
-1 votes
1 answer
52 views

The book says 27 terminals but I only see 10. Where are they?

On page 103 of Mike Sisper's Introdution to Theory of Computation, it says that the grammar has 27 terminals (26 being the letters of the English Alphabet and 1 being the space character) but in the ...
Sbavert's user avatar
  • 51
1 vote
2 answers
92 views

Need to create CFG that requires sum of other letters

I have a homework assignment that requires me to create CFG $G$ for $$L = \{a^i b^{i+j+k} c^j d^k\}$$ so that it can accept words like ab, aaabbbbd, abbbcd, but it should not accept abba, aabbbbbc, or ...
Sefa Kalkan's user avatar
0 votes
1 answer
64 views

Pushdown Automata Construction

I had an assignment in which I had to design a pushdown automata that recognizes the language ${w \in [a,b,c]^*|w }$ have the same number of "ab" and "ba". Tried to make a pushdown ...
Jack Vork's user avatar
4 votes
0 answers
63 views

Is the following language recognizable by a visibly pushdown automaton?

Consider the alphabet $\Sigma = \Sigma_c \cup \Sigma_i \cup \Sigma_r$ separated into call, internal, and return letters. Assume that $c \in \Sigma_c, r \in \Sigma_c$, and $a \in \Sigma_i$. I have a ...
VisiblyPushdownPerson's user avatar
0 votes
0 answers
152 views

prove that Every DPDA has an equivalent DPDA that always reads the entire input string

I am reading Michael Sipser's book Introduction to the Theory of Computation and in the section 2.4(chapter 2 and DCFLs section) there is a proof for the lemma that says "Every DPDA has an ...
emdhdr's user avatar
  • 1
0 votes
1 answer
495 views

PDA for equal number of as and b's where n>=1

How to design Push Down Automata for a language that has equal number of a's and b's where $n \ge 1$? I got how to do it for $n \ge 0$, not able to get it for $n \ge 1$.
user avatar
3 votes
2 answers
114 views

Implementation details of "transitions" of Non-deterministic push-down automata

I am reading "Introduction to the Theory of Computation" 3rd edition ~ by Michael Sipser, page 113-114 - topic: "Context free languages, push down automata" He states that the ...
Pratik Hadawale's user avatar
0 votes
1 answer
207 views

PushDown automata for a^(n) b^(2n) c^(2n) d^(n)

i got this question in a theory of computation quiz "give pda for a^(n) b^(2n) c^(2n) d^(n)" i am arguing that there is no pda for that question but our ta says that we can push 5x to the ...
ambiguous student's user avatar
0 votes
1 answer
71 views

What characteristics would a PDA $A$ where $L(A)=\Sigma^*$ have?

I understand that the problem of whether a PDA accepts all strings is undecidable. However that doesn't mean such PDAs exist. To start, I'm working under the assumption that a PDA must read it's ...
Gabe Kelly's user avatar
0 votes
1 answer
101 views

Intersection of CFL and DCFL

Is CFL $\cap$ DCFL = CFL, always true? CFL - Any Context Free Language DCFL - Any Deterministic Context Free Language
Chaitanya Kale's user avatar
1 vote
1 answer
140 views

Shuffle of a DCFL and a regular language

This is problem 88 from Miscellaneous exercises of Kozen's "Automata and Computability". The shuffle $A||B$ of two languages $A$ and $B$ is defined as $\{w \mid w = a_1b_1\ldots a_kb_k,$ ...
ayan's user avatar
  • 13
0 votes
1 answer
115 views

Push Down Automata

I am learning about context free languages. I understand how $\{a^nb^nc^n|n>0\}$ can be shown to be not context free using the pumping lemma for CFL's. Intuitively however it seems that a pushdown ...
Manan's user avatar
  • 1
1 vote
1 answer
1k views

Understanding this PDA for non-palindromes over {0,1}

I found this PDA online that accepts all non-palindromes over {0,1}. However, I can't seem to understand how it would accept, say "01011", and not accept "101101". Can someone help ...
stylusss's user avatar
0 votes
1 answer
42 views

Context Free Language Twist [duplicate]

I am trying to recognize a particular language, L= {a^n b^k | n<=k<=2n} and according to me it should not be CFL, as i can see two comparision i.e. firstly number of a is compare to keep count ...
Niraj Jain's user avatar
2 votes
0 answers
140 views

Minimizing DPDA

Is there an efficient algorithm for minimizing a deterministic PDA in terms of states? Is it even computable? I know that it is not possible to minimize a PDA in general, but my question is about ...
Peter Lenkefi's user avatar

1
2 3 4 5
12