state machines with stacks, capable of accepting the set of context-free languages.
0
votes
0answers
30 views
Pushdown automation where number of letter `a` is at least as twice as letter `b` in the word [duplicate]
I have talked to my friend and he said this is the only place somebody could know how to solve it. It is the only exercise(from around 80) from exam revise I just do not know how to do at all.
Create ...
3
votes
1answer
79 views
Pushdown automation where number of letter `a` is at least as twice as letter `b` in the word
I have talked to my friend and he said this is the only place somebody could know how to solve it. It is the only exercise(from around 80) from exam revise I just do not know how to do at all.
Create ...
-2
votes
1answer
55 views
PDA with 2 stacks
I am doing homework in Formal Languages. I urgently need a language which can be recognised by 2 PDA's but not with 1 PDA. Thanks
2
votes
1answer
61 views
PDA for this context-free grammar
I have the following CFG $G$:
$$ \begin{align}
S &\rightarrow aAbb \mid aaBb \\
A &\rightarrow aAbb \mid \epsilon \\
B &\rightarrow aaBb \mid \epsilon \\
\end{align} $$
I have to create a ...
-1
votes
1answer
52 views
Compare two words using a Pushdown Automaton
I'm doing a college work about automatons. In one exercise I've to compare two words with five letters each one, but I don't know how to do it, do you have any tutorial or example for that?
5
votes
1answer
58 views
prove no DPDA accepts language of even-lengthed palindromes
How do you prove that the language of even-lengthed palindromes, i.e.,
$L=\left\{ ww^R \mid w\in \left\lbrace 0,1 \right\}^* \right\}$, can not be accepted by a determinsitc Push-Down-Automaton?
Is ...
11
votes
0answers
209 views
Is this strange language context free?
Is the following language context free: $L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^*\text \{ \epsilon \} \ ,\ \mid u \mid = \mid v \mid \ , \ u \not= v \ , \ \mid x \mid = \mid y \mid \ , \ x \not= y \ ...
1
vote
2answers
109 views
Converting CFG to PDA
I have the following CFG,
$S \rightarrow CB$
$C \rightarrow aCa \text{ }|\text{ } bCb \text{ }|\text{ } \text{#}B$
$B \rightarrow AB \text{ }|\text{ } \varepsilon$
$A \rightarrow a\text{ }|\text{ }b$
...
2
votes
1answer
106 views
Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free?
Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free ?
If we fix $n \in N$ then we know that the language $L = \{ a^ib^j \mid \ \forall \ 1 \le k \le n \ , \ \ j\neq ki \} $ is ...
2
votes
2answers
83 views
Designing a PDA w/o $\epsilon$-moves and $\leq 2$ states to accept an $\epsilon$-free CFL by final state
I understand that any CFL can be accepted by a PDA by final state or empty store but I have been rather stumped by this question.
The question states that the PDA has at most 2 states. Clearly 1 will ...
8
votes
1answer
199 views
Is the language $\{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free?
Is the language $ L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free ?
I guess that it's not context free because it seems too complicated for a PDA to decided whether 2 numbers ...
2
votes
1answer
41 views
Cartesian construction of PDA and DFA
How would I go about using Cartesian construction to find the intersection between a PDA and a DFA?
Is there another term for Cartesian construction? Would it be similar to the procedure for finding ...
0
votes
1answer
66 views
Convert CFG to PDA
Is there any set of rules or methods to convert any context free grammar to a push down automata?
I already found some slides online but I wasn't able to understand them.
In slide 10 he speaks ...
2
votes
1answer
40 views
Syntax of a Pushdown Automata transition function
I just learned PDAs in class today, but am having problems understanding the syntax of the transition function. Could someone please explain to me the meaning of this syntax:
$\delta(q, \lambda, S) = ...
0
votes
1answer
48 views
How to generate a pushdown automata for accepting a language?
I have an exercise in my book to come up with a pushdown automaton accepting a language.
The exercise is to come up with a state diagram for the PDA accepting the language of all odd-length strings ...
3
votes
2answers
54 views
Give CFG and PDA for the words that start and end with the same symbol
I need to give a PDA and CFG for a language that contains all binary strings that start and end with the same symbol. I've created the CFG with no problem, but I'm stuck with the PDA and don't quite ...
1
vote
1answer
74 views
Is $L= \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $ context free?
$L = \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $
Is this language a context free language?
If yes give a PDA. If no, give a proof.
The pumping lemma for context free languages doesn't seem to work ...
6
votes
1answer
82 views
Is there a strictly non-deterministic one-counter language whose complement is one-counter?
Let
$A= \{L \mid L \;\text{is one-counter and \(\bar{L}\) is also one-counter} \}$
Clearly, $\text{Deterministic one-counter} \subseteq A$
Is it the case that $ A = \text{Deterministic ...
3
votes
1answer
78 views
Proving that a specific language is a CFL, and that another language is not a CFL
I have two languages $C_1$ and $C_2. \left(\Sigma=\{0,1\}\right)$:
$C_1=\left\{xyz\mid x,z \in \Sigma^*, y \in \Sigma^*1\Sigma^*, \text{ where } |x|=|z| \geq |y|\right\}$, and $C_2=\left\{xyz\mid x,z ...
1
vote
2answers
104 views
Constructing PDA for $a^{2n} b^{3n}$
So I have been given the task of creating an PDA that recognises the language
$\{a^{2n} b^{3n} \mid n = 0,1,2,\dots\}$.
Am I right in thinking that it needs to have at least 3 times number of $b$'s ...
3
votes
3answers
239 views
Constructing PDA to accept language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ }
I'm trying to understand the approach to constructing a PDA which accepts the language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ }
1
vote
1answer
254 views
Push down automata for $\{a^n b^n c^n | n \ge 0\}$
I am learning about context free languages.
I understand how $\{a^n b^n c^n | n \ge 0\}$ can be shown to be not context free using the pumping lemma for CFL's.
Intuitively however it seems that a ...
1
vote
3answers
147 views
Eplaining why a grammar is not LL(1)
I need some help with explaining why a grammar is not LL(1).
Let us take the following grammar:
$$
\begin{align}
S \rightarrow & aB \mid bA \mid \varepsilon \\
A \rightarrow & aS \mid bAA \\
...
0
votes
1answer
97 views
Formal Languages - Expressive power of Formalisms
I need help with the following question:
Order the following formalisms according to their expressive power:
placing A before B means that any language definable by A is definable
by B. Also state ...
3
votes
1answer
108 views
why are deterministic PDAs not closed under concatenation?
I can understand that they are not closed under concatenation because without non determinism, PDA cannot decide whether to loop in the first PDA or jump to the next one.
But can someone prove this ...
5
votes
1answer
322 views
Construct a PDA for the complement of $a^nb^nc^n$
I am wondering if this is even possible, since $\{a^n b^n c^n | n \geq 0\} \not\in \mathrm{CFL}$. Therefore a PDA that can distinguish a word $w\in\{a^n b^n c^n | n \geq 0\}$ from the rest of ...
3
votes
1answer
90 views
Deterministic context-free languages are closed under regular right-product
I am looking for a proof for the following problem:
For languages $L$ and $R$, if $L$ is deterministic context-free
and $R$ is regular, then $LR$ is a deterministic context-free
language.
...
1
vote
1answer
165 views
How can one simulate a PDA with a FIFO queue PDA?
I'm trying to figure out how a pushdown automata (PDA), which we know uses a stack (LIFO) can be simulated by a queue (FIFO). I understand that in a regular PDA, we only have access to the top most ...
2
votes
2answers
122 views
CFG and PDA for the grammar that has perfectly nested parentheses and brackets
I gotta make a CFG and PDA for the grammar that has perfectly nested parentheses and brackets.
$\qquad\begin{align}
S &\to [S] \\
S &\to (S) \\
S &\to SS \\
S &\to \varepsilon
...
2
votes
2answers
259 views
How do I show that whether a PDA accepts some string $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?
How do I show that the problem of deciding whether a PDA accepts some string of the form $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?
I have tried to reduce this problem to another undecidable ...
2
votes
3answers
195 views
Constructing deterministic PDA for not regular language
Let the input alphabet be $\Sigma = \{a,b,c\}$ and L be the language of all words in which all of the a’s come before all of the b’s and there are the same number of a’s as b's and arbitrarily many ...
0
votes
2answers
214 views
When generating a PDA from a CFG do I have a receiving state?
Thw Wikipedia article on Pushdown automata doesn't explain what the receiving state is for the generated PDA it just states that there is but one state.
2
votes
1answer
227 views
Context-free grammar to a pushdown automaton
I'm trying to convert a context free grammar to a pushdown automaton (PDA); I'm not sure how I'm gonna get an answer or show you my progress as it's a diagram... Anyway this is the last problem I have ...
2
votes
1answer
176 views
Eliminating useless productions resulting from PDA to CFG converison
In my class we used a Pushdown Automata to Context Free Grammar conversion algorithm that produces a lot extraneous states.
For example, for two transitions, I am getting the following productions
...
5
votes
0answers
98 views
How to prove that ε-loops are not necessary in PDAs?
In the context of our investigation of heap automata, I would like to prove that a particular variant can not accept non-context-sensitive languages. As we have no equivalent grammar model, I need a ...
8
votes
1answer
248 views
Decide whether a context-free languages can be accepted by a deterministic pushdown automaton
Given a context-free grammar G, there exists a Nondeterministic Pushdown Automaton N that accepts exactly the language G accepts. (and visa versa)
There may also exist a Deterministic Pushdown ...
9
votes
2answers
344 views
Does the language of Regular Expressions need a push down automata to parse it?
I want to convert a user entered regular expression into an NFA so that I can then run the NFA against a string for matching purposes. What is the minimum machine that can be used to parse regular ...
5
votes
3answers
408 views
If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?
I'm am stuck solving the next exercise:
Argue that if $L$ is context-free and $R$ is regular, then $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} $ (i.e. the right quotient) is ...
2
votes
1answer
617 views
How does a two-way pushdown automaton work?
Note that by "two-way pushdown automaton", I mean a pushdown automaton that can move its reading head both ways on the input tape.
I recently had the question of determining the computational power ...
2
votes
6answers
2k views
Are Turing machines more powerful than pushdown automata?
I've came up with a result while reading some automata books, that Turing machines appear to be more powerful than pushdown automata. Since the tape of a Turing machine can always be made to behave ...
16
votes
1answer
700 views
Are there inherently ambiguous and deterministic context-free languages?
Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise.
Let us call a context-free language ...
1
vote
1answer
284 views
Converting a context free grammar to a PDA — is my solution correct?
I'm reviewing for my midterm and wanted to post this to see if anyone can spot any errors. Im supposed to make a PDA that recognizes this CFG:
$\qquad\begin{align}
S &\to R1R1R1 \\
R &\to ...
