state machines with stacks, capable of accepting the set of context-free languages.

learn more… | top users | synonyms

0
votes
2answers
29 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
10 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
24 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 ...
1
vote
0answers
25 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
37 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
10 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
33 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
75 views

Find a pushdown automaton for $ \{x\#y \mid x,y \in \{0,1\}^{\ast} \wedge x \neq 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
31 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
70 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
26 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 ...
10
votes
1answer
295 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
58 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
18 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
31 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
112 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
49 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
188 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
48 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
49 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' ...
0
votes
0answers
17 views

non-regular context free language with logarithmic stack usage [duplicate]

Can you suggest a context-free language $L$, which is: non-regular has a PDA which accepts all $w\in L$ and uses maximum stack space of $\log(|w|)$.
3
votes
2answers
91 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
262 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 ...
4
votes
5answers
160 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
91 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
77 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
152 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 ...
1
vote
1answer
31 views

Why is it that the transition function for DPDA's only works for 1 alphabet symbol, and 1 stack symbol?

Why is it that the transition function for DPDA's only works for 1 alphabet symbol, and 1 stack symbol? Say f is the transition function, why does having ...
0
votes
2answers
48 views

what is the best way to approach the construction of nondeterministic PDA's?

I'm trying to construct a PDA for $L = \{w0^i1^j \mid w\text{ ends in } 01 \wedge 2i=3j\}$. My understanding is that I have to first accept an arbitrary number of zeros and ones and then ...
2
votes
1answer
116 views

Language of binary strings divisible by 7

There was a question something like, "Consider the language of all integers converted to binary form. The language of all strings divisible by 7 is : 1) Recognizable by a finite-automaton. 2) ...
1
vote
2answers
144 views

PDA recognising all strings with a $1$ in the second half

My professor gave us an old exam to look over for our final exam and I am having a hard time understanding the push down automata problem he gave. In the problem it says: Let $\Sigma = \{0,1\}$ ...
1
vote
2answers
65 views

Is it possible to write an HTML compiler with no mutable state?

That's probably a vague question but allow me to try and give an example: My compiler does transformations on HTML (from HTML to HTML). It scans a flattened DOM tree, and relies on lookbehinds (on ...
0
votes
1answer
66 views

PDA - Sum of Two Characters = Sum of Two Other Characters

For one problem I have to solve, I'm given a Language: L = {a^r b^s c^t d^u | r+s = t+u} And from it told to construct a PDA that accepts it. I can construct a ...
-1
votes
1answer
64 views

Simple Pushdown Automaton

I'm currently learning about PDAs and their power when constructing them from Context-Free Grammars, however I'm still unsure of how to properly construct a CFG, and then a PDA from that CFG. In the ...
2
votes
0answers
22 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
1answer
57 views

Can a DPDA be created for a Language which includes the null string?

Can a DPDA be created for a Language which includes the null string? The way I understand it, in a DPDA, you can have at most 1 move from any instantaneous description Delta(q,a,Z) where q is a ...
1
vote
2answers
67 views

What is the purpose of ϵ-transitions in PDA?

$A = \{a^i b^j c^k\mid i = j\text{ or } j = k; i, j, k \ge 0\}$. In its push down automaton should not there be the red colored transition instead of the black colored one?
3
votes
1answer
46 views

Is “duplicate” in RPN enough for replacing variable binding in term expressions?

I try to work out some consequences of storing (or "communicating"/"transmitting") a rational number by a term expression using the following operators: $0$, $\mathsf{inc}$, $\mathsf{add}$, ...
0
votes
1answer
66 views

Intersections of some context-free languages

Suppose We have Some language as follows: $L_1=\{w^* | w=x \text{ and } x \in \Sigma^*\}$ $L_2=\{ww^R ww^R | w \in ( \Sigma + \Sigma)^*\}$ $L_3=\{w | w=xy, x,y \in \Sigma^*, y \text{ is a ...
4
votes
1answer
371 views

Are DCFLs closed under reversal?

According to this chart, DCFLs are closed under reversal. However, I am not convinced as the intuitive proof (reversing the arrows of the controlling finite state machine and switching the pushes and ...
-2
votes
1answer
137 views

Pushdown Automata Challenge

I read one old-midterm exam on Automata. consider: the language that accepted by above pushdown automata is not generated by which of the following grammar? 1) S->aBaa|a$\epsilon$ ...
-1
votes
1answer
39 views

Do NFAs with ϵ-transitions accept languages that no PDA can?

Is it correct to say that there are languages that a NFA with epsilon recognizes but a PDA is not? I think that it is wrong but I cannot find a suitable explanation.
1
vote
1answer
154 views

Non Deterministic PDA accepted language not clear

This is a PDA from the lecture slides I'm using: They say it accepts all words that contain double a's. While it makes some sense it's not full proof. What prevents the second a to be read in the ...
4
votes
2answers
60 views

Incorporating newline-as-statement-terminator heuristics into context-free languages

Several block structured languages (Scala, Go, Ruby, Julia, Quorum, ...) use semicolons as statement terminators, but allow newlines instead of semicolons under certain circumstances. My question is: ...
0
votes
1answer
53 views

Is there a PDA for every Type 3 Grammar?

we learned that for every type 2 grammar G exists a PDA A with L(A) = L(G). But does for every type 3 grammar G exist a PDA A_G with L(A_G) = L(G)? I think it does, because type 2 grammar is a subset ...
-1
votes
1answer
79 views

writing a Context free grammar for a language [closed]

Hi I have two question about this language: L = {a^i b^j c^k | i = 2*j OR j=2*k } 1)Finding a CFG 2)If in condition part we put AND instead of OR , is this language remains CONTEXT FREE or not ?? ...
2
votes
0answers
159 views

Good introductions to Formal Language Theory and Formal Grammars

Does anyone know any good introductions to Formal Language theory and Formal Grammar, that cover the mathematical basis of Syntax and things like context free grammars and pushdown automata. In ...
9
votes
1answer
116 views

Computing the intersection of two NPDA where it is possible

Apropois to Raphael's suggestion on Intersection of two NPDAs: Let $A_1$ and $A_2$ NPDA for context-free languages $L_1$ and $L_2$, respectively. Assuming that we know that $L = L_1 \cap L_2$ is ...
5
votes
2answers
66 views

Intersection of two NPDAs

Is there a way to take the interection of two NPDAs? I can't seem to find anything that can make that happen, but it seems like the type of thing that is should be relatively trival.
1
vote
2answers
254 views

How many states when converting CFG to PDA

When converting a CFG to a PDA I know that you get three main states, Qstart, Qloop and Qaccept. But Qloops will need a various amount of states, and my question is how many? Is there a way to find ...