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

learn more… | top users | synonyms

4
votes
2answers
34 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
37 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 ...
0
votes
0answers
15 views

How would i design a PDA that accepts order of sentence? [duplicate]

How would i design a PDA that accepts order of sentence. In Natural Language Processing, context free grammars are used to identify valid English sentences from invalid once. For instance, ‘Lorem ...
-1
votes
1answer
30 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
82 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 ...
0
votes
0answers
70 views

Constructing nondeterministic pushdown automata

I having trouble constructing NPDAs for these two languages: $L_1 = \{a^nb^m \mid 2n \le m \le 3n\}$ $L_2 = \{a^nb^mc^k \mid n = m \: or \: m \ne k\}$ Would these be the proper states for the first ...
9
votes
1answer
91 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
58 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.
0
votes
2answers
78 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 ...
1
vote
1answer
40 views

Proving a language is not a regular language but a context free language [duplicate]

I have the languages $L_1$ and $L_2$ such that $L_1 = \{a^nba^n :n \in N\}$ and $L_2 =\{a,b\}^*\setminus L_1$. I want to prove that $L_2$ is not a regular language. I know that to prove that $L_2$ is ...
2
votes
1answer
51 views

Why Deterministic PDA accepts $\epsilon$ input but DFA not

I was going through a deterministic PDA that accepts $wcw^R$ (described in Ullman's textbook), in which the last transition is given as $(q_1,\epsilon, Z_0)\to(q_2,Z_0)$, where $q_2$ is the final ...
-1
votes
1answer
71 views

A NPDA for the language $L = \{w \mid w \in \{a,b,c\}^*, n_c(w) = n_a(w) + n_b(w)\}$

Consider the language $L = \{w, w \in \{a,b,c\}^*, n_c(w) = n_a(w) + n_b(w)\}$, where $n_q(\omega)$ is defined to be "the number of $p \in \omega$. I have tried a couple of PDA's that follow this ...
1
vote
2answers
112 views

Why are pushdown automata countable? [closed]

I began a chapter in a textbook on computational theory where they begin to talk about decidable languages. The problems in this section are pretty confusing and I honestly don't know how to begin ...
2
votes
1answer
100 views

Creating a Deterministic Push Down Automata

I saw this old post on stack overflow of a PDA that accepts a language where there are exactly twice as many a's as there are b's. The image they used is below and so is the link to the post itself. ...
1
vote
0answers
33 views

Are all PDA equivalent to two-state-PDA? [closed]

We know algorithm to convert each PDA in the underlying grammar that generates the language the PDA recognize. But we have also the algorithm for creating a two state pda from a grammar. This ...
5
votes
1answer
89 views

How to find a Deterministic PDA for an intersection of languages

There are two languages, $\qquad L_1 = \{w\in\{a,b\}^*: N_a\leq N_b\}$ and $\qquad L_2=\{w\in\{a,b\}^*: N_b\leq 2N_a\}$ where $N_a$ means the number of occurrences of $a$ in the string $w$. Same ...
3
votes
2answers
182 views

How to get 2-state PDA for CFG?

I'm studying for my Computing languages test and there's one idea I'm having problems wrapping my head around, as far as I know for any Context Free Grammar (CFG), we can design a 2-state Pushdown ...
1
vote
0answers
45 views

Equivalency of two pushdown automata

How would one go about proving that one PDA that may only pop one symbol from its stack per transition, is equivalent to a second PDA that is allowed to pop any number of symbols? That is a PDA with ...
2
votes
3answers
86 views

Relaxing the stack in a push down automata

Given a non-deterministic push down automata (we define "accept" here using accept states), if we assume any operation popping from the stack and checking if the top of the stack contains some symbol ...
6
votes
3answers
172 views

Demonstrate that DPDA is closed under complement by construction

I've been trying for quite some extended time to find a construction so that I can formally demonstrate that a deterministic PDA is closed under complementation. However, it happens that every idea I ...
1
vote
2answers
230 views

Decide whether a DFA accepts the empty language

Let $X = \{\langle M \rangle\ |\ M\text{ is a finite state machine and }L(M) = \emptyset\}$ where $\langle M \rangle$ is an encoding of the machine $M$. Is $X$ Turing decidable? Why or why not?
2
votes
2answers
94 views

Is $\{w:w\in(a+b+c)^*, n_a(w) > n_b(w)>n_c(w)\}$ context-free?

So I've been given the following language on an assignment. It is the only question I have left of 10, and I've been racking my brains out trying to solve it for hours. $$L=\{w:w\in(a+b+c)^*, ...
-2
votes
2answers
92 views

help with the probability of acceptance of a Nondeterministic Pushdown automata

I have this nondeterministic pda: $$\Sigma= \{a,b,c\}$$ and $$ L=\{\omega\ \epsilon\ \Sigma^*\ |\ \omega\ = \alpha\beta\beta^R\gamma\ and\ \alpha,\beta,\gamma\ \epsilon\ \Sigma^*\ and\ |\beta|\ ...
0
votes
1answer
83 views

Does this pushdown automaton describe the language {$a^n b^n c^i \in \{a,b,c\}^*\ |\ n \ge 0,i\ge 0$}?

I've just been learning about pushdown automata and I'm trying to create one that describe the following language: {$a^n b^n c^i \in \{a,b,c\}^*\ |\ n \ge 0,i\ge 0$} What I have is the following: ...
0
votes
1answer
50 views

How do you obtain transition relation of a PDA?

I know how to figure out the start state, accepting state, input alphabet, and all that stuff. But how do you develop the transition relation of a PDA? For an FSM, (q0,a),q1) means if you start at q0 ...
0
votes
0answers
68 views

Creating PDA for {xy such that |x|=|y| and x ≠ y} [duplicate]

I'm trying to create a PDA for $\{xy \mid |x|=|y| \text{ and } x \ne y\}$ over the alphabet $\Sigma = \{a, b\}$. But I don't know how the PDA will know if the two strings $x$ and $y$ are not equal. ...
2
votes
1answer
86 views

Can we push and pop both at a single transition in a PDA?

Let say I have a pda : δ(q1,a,Z)=(q2,aZ) δ(q2,a,aZ)=(q2,bZ) Is this allowed.... you can see that in δ(q2,a,aZ)=(q2,bZ), we are basically popping 'a' and pushing 'b' for a single transition... Is ...
0
votes
1answer
495 views

Pushdown automaton for complement of $L = \{ ww \mid w \text{ in } (0,1)^*\}$

I want to be able to describe the idea behind the pushdown automaton (no tables or diagrams). So, I already know that $L = \{ ww \mid w \text{ in } (0,1)^*\}$ is not context free. Since CFL are not ...
1
vote
1answer
149 views

Approaches to Solve PDA

There is a saying by Computer Science Professor's everywhere : ...
1
vote
1answer
193 views

Prove that {0^{n^3} | n≥0} is not context free

I'm not very comfortable with pumping lemma for context-free grammar. I understand the sufficient conditions that must hold but proving it gets me everytime. For example, I need to prove whether $L = ...
4
votes
2answers
821 views

Constructing a PDA for the language $\{a^m b^n : m < 2n < 3m \}$

I'm having a lot of trouble constructing a PDA for the language: \begin{equation*} \{a^m b^n : m < 2n < 3m \} \end{equation*} I know if I push a symbol for each $a$ I see, then pop 2 symbols ...
0
votes
3answers
89 views

Determine whether two languages are context free

(1) $L_1 = \{a^ib^{i+j}c^j|i,j\geq 0\} $ (2) $L_2 = \{xy | x,y \in \{0,1\}^*, x \neq y, |x| = |y| \}$ I doubt that $L_1$ is CFL. I've been trying to go with the string $s$ = $a^pb^{2p}c^p$. Thus, we ...
1
vote
1answer
579 views

Use pumping lemma to show L is not context free

Show that L = $\{0^{2^n}| n\geq 0\}$ is not a context free language. Let string $s = 0^{2^p}$. Then we know we can write $s$ as $s = uvxyz$. I know that |vy| > 0 and $|vxy| \leq p$. So how do I ...
1
vote
0answers
105 views

Constructing a Context Free Grammar for checking non-equality of strings

I have been studying the book Introduction to Computation by Michael Sipser on my own, and I'm stuck on this exercise from the chapter on Pushdown Automato and Context-Free Languages. The exercise is ...
3
votes
1answer
334 views

Definition of deterministic pushdown automaton

Wikipedia Pushdown automaton (as of aug 16, 2013) states: In general, pushdown automata may have several computations on a given input string, some of which may be halting in accepting ...
6
votes
2answers
125 views

Push Down Automatons “guess” - what does that mean?

I realize non-deterministic pushdown automata can be an improvement over deterministic ones as they can "choose" among several states and there are some context-free languages which cannot be accepted ...
2
votes
1answer
231 views

If a parser can parse a non-deterministic grammar, is the parser non-deterministic?

I've written a recursive-descent parser generator, and I'm trying to classify it (call me a cowboy coder if you must). According to wikipedia, S → 0S0 | 1S1 | ε, ...
5
votes
1answer
147 views

Reference request: proof that if $L \in DCFL$, then $L \Sigma^* \in DCFL$

So, it's fairly easy to prove that if $L \in DCFL$, then $L \Sigma^* \in DCFL$. Basically, you take the DPDA accepting $L$. You remove all transitions on final states, and then for each $a \in \Sigma$ ...
6
votes
2answers
129 views

Myhill-Nerode style characterization of CFL?

Define the Nerode equivalence over a language $L \subseteq \Sigma^{*}$ as $u \sim_L v$ iff $uw \in L \Leftrightarrow vw \in L$ for every $w \in \Sigma^{*}$. The Nerode equivalence ${\sim}_L$ has ...
7
votes
1answer
152 views

Paper with proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$ is not Deterministic Context Free?

These lecture slides sketch a proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$ cannot be accepted by any Deterministic Pushdown Automaton. Unfortunately, the slides give ...
0
votes
0answers
31 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
139 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 ...
-3
votes
1answer
799 views

PDA with 2 stacks

I urgently need a language which can be recognised by 2 PDA's but not with 1 PDA.
2
votes
2answers
214 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
222 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
292 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 ...
20
votes
3answers
814 views

Is this strange language context free?

Is the following language context free: $L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} $ ? I think that it's not context free but I'm having a hard time proving ...
1
vote
2answers
432 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$ ...
3
votes
2answers
250 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
396 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 ...