Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.

learn more… | top users | synonyms

2
votes
1answer
13 views

Proving that if $L=\{ a^n b^n c^n \colon n\ge 0 \}$ than $L\notin CFL$

I'm going over "Introduction to the Theory of Computation" by Michael Sipser in which there's an example of using the pumping lemma for CFLs to prove that $L=\{ a^n b^n c^n \colon n\ge 0 \}$ is not a ...
0
votes
0answers
12 views

CFG. Ensure that $n\neq m$ twice in $L=\{a^m b^n c^m d^n, m\neq n\}$

During the formal language exam, the professor allowed to find a CFG to following language: $\{a^m b^n c^p d^q, m\neq n\wedge p\neq q\}(1)$, because neither he saw a solution (He passed a test without ...
3
votes
0answers
18 views

How much bigger can an LR(1) automaton for a language be than the corresponding LR(0) automaton?

In an LR(0) parser, each state consists of a collection of LR(0) items, which are productions annotated with a position. In an LR(1) parser, each state consists of a collection of LR(1) items, which ...
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 ...
-3
votes
1answer
44 views

How to convert this type of languages to Context Free grammar?

As I've already asked my Question about the solving Context Free Grammar $L = \{a^n b^m c^p \mid n = m + p + 2\}$ Can this language be defined by a Context Free Grammar? Now i have just changed ...
-1
votes
1answer
126 views

Does every language that fulfills the regular Pumping conditions also fulfill the context-free ones?

Let L be a language that fulfills the properties implies by the Pumping lemma for regular languages. Does L necessarily fulfill the corresponding properties of the Pumping lemma for context-free ...
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 ...
2
votes
2answers
129 views

Can this language be defined by a Context Free Grammer?

I was solving one of my practice questions, defining a language with Context Free Grammar Productions , but I am stuck on one question , Here are my attempt: Question: $L = \{a^n b^m c^p \mid n = m + ...
0
votes
1answer
32 views

Proving that a set of grammars for a given finite language is decidable [duplicate]

Let the language $$L = \left\{ \langle G \rangle \ |\ L(G) = \{1,\ldots , 1000\}, \text{ G is a CFG }\right\}$$ Prove that $L \in R$. Well, I think that for a start we need to check whether or ...
1
vote
0answers
54 views

Are DCFLs closed under concatenation with a regular language?

I have found various opinions saying they are (a link to one is given in D.W.'s comment). However, a proof that DCFLs themselves are not closed under concatenation found here on StackExchange seems to ...
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
votes
1answer
22 views

Chomsky Normal Form-remove unit production

In the step of removing unit productions when converting a grammar to Chomsky normal form, I sometimes found that the variables may end up having the same production bodies. Is this possible? If so, ...
0
votes
0answers
58 views

The pumping lemma - Proving that this language is NOT context free

I would like to find out if this language is context free or not: $\qquad L=\{a^{i}b^{j}c^{k} \mid i<j,i+2j+3<k\}$. I've tried to apply the pumping lemma taking out $w=a^n b^{n+1}c^{3n+6}$ ...
0
votes
1answer
46 views

Context free grammar for this language [duplicate]

Is this language Context Free? $L=\{a^{n+3} b^{2m} \mid n \neq m \}$ I think that I could split the languages into $L_1$ and $L_2$ with the conditions $n<m$ and $n>m$, provide 2 CF grammars ...
0
votes
1answer
66 views

Using the pumping lemma to prove that a language is context-free [duplicate]

I am new to automata theory. Could you give me a little hand with the correct use of the pumping lemma? I understand now how to proof a language is not context-free, but how do I use the pumping ...
0
votes
0answers
20 views

Prove this language is not CFL [duplicate]

I have this language: $L = \{a^{n+2} b^m a^{2n} b^{3n}\mid n,m >=0 \}$ and I am trying to prove that it is not CFL. I assumed that my word is $a^{p+2} b^m a^{2p} b^{3p}$ (where $p$ is the pumpung ...
0
votes
1answer
38 views

How can I prove this language is not CFL? [duplicate]

I have a question to find out that $L = \{a^m b^n\mid n>0, m - is prime \}$ is CFL or not. I know that it is not a CFL. But I don't know how to prove that. I know how to prove that $L = \{a^m\mid m ...
0
votes
0answers
107 views

For which subset of all CFG can we show that $L=\mathcal{L}(G)$

Raphael explained in the comments that there are no algorithms to show $L=\mathcal{L}(G)$ for context-free grammar. So we have to reduce our expectations and try to find a proof method. In this ...
-1
votes
1answer
27 views

What would be CFG for all strings which does not contain bbb?

Is there a way to get complement? Following is my solution for CFG of all strings that DON'T contain bbb. ...
-2
votes
1answer
29 views

CFG for all string that don't end at ba?

Here is my solution: S-> Sab|Sbb|Saa S->aS S->bS S->ε Is this solution right?
-1
votes
0answers
41 views

Is this language CFL or not? [closed]

I have a question to find out that $L = \{a^{4k} b^l a^k\mid k\geq0, l\geq1 \} + \{a^i b^j\mid i\ne j\}$ is context free or not. I don't know from where to start solving it. I know that CFL's are ...
0
votes
1answer
40 views

How to prove that the language { ww | w ∈ {a,b}* } is / isn't context free? [duplicate]

Is the language { ww | w ∈ {a,b}* } context free? I have tried to create a pushdown automaton but I didn't find any solution. I think you need a queue and not a stack. Is there a way to prove this ...
0
votes
1answer
75 views

Is the language $L=\{a^{2^{n}} \mid$ n is a natural number$\} $ context free?

I have to determine, and prove, whether the language $L=\{a^{2^{n}} \mid$ n is a natural number$\}$ is context free or not (if it is by a grammar and not by the pumping lemma). I tried to construct ...
6
votes
1answer
50 views

Smallest class of automata model whose corresponding language class contains CFL and is closed against (dis)allowing nondeterminism in the model

From a comment, an interesting question popped up. The class of CFLs (the languages recognized by PDAs) are obviously not closed under nondeterminism - what I mean by this is that deterministic PDAs ...
8
votes
0answers
56 views

Machines for context-free languages which gain no extra power from nondeterminism

When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines. For the ...
3
votes
1answer
52 views

Removing left-recursion in grammar while maintaining left-association of operator

I have a problem with this exercise: Let G be the following ambiguous grammar for the λ-calculus: E → v | λv.E | EE | (E) where E is the single ...
1
vote
2answers
91 views

Tips for creating “Context Free Grammar” [duplicate]

I am new to CFG's, Can someone give me tips in creating CFG that generates some language For example $L =\{ w v w^R \mid v,w\in \{a,b\}^*\wedge|v| \text{ is even } \}$, where $w^R$ is the reverse ...
20
votes
2answers
2k views

What does “context” in “context-free grammar” refer to?

There are lots of definitions online about what a Context-Free Grammar is, but nothing I find is satisfying my primary trouble: What context is it free of? To investigate, I Googled "context ...
0
votes
0answers
36 views

Context-free with single terminal symbol — regular language [duplicate]

I have the following problem to solve: Show that if G is a context-free grammar and Σ consists of just one terminal symbol, then L(G) is regular. It is problem 4.26 from the book "Formal models of ...
-2
votes
1answer
48 views

Is the language given by this CFG regular? [duplicate]

S → AB | C A → aAb | ab B → cBd | cd C → aCd | aDd D → bDc | bc How can I prove that this language is regular or not? I need your help. It also has two ...
1
vote
1answer
26 views

Unambiguous but nondeterministic context-free language?

Whenever deterministic context-free languages are discussed, the webpage/textbook would always give a side note saying that although deterministic context-free languages are never ambiguous, ...
6
votes
1answer
79 views

TM recognizing $0^n1^n$ requires Ω(log n) space

I am trying to prove that any deterministic 1-tape Turing Machine which recognizes the language $L = \lbrace{0^n1^n | n \geq 0 \rbrace}$ requires $\Omega(\text{log }n)$ space. I believe this can be ...
-3
votes
1answer
28 views

Chomsky Normal Form of |a|<|b| [closed]

Hello Everyone I was hoping I could ask you to check to my work on this CNF, These are a pain to me and I want to make sure I'm doing it right the first time ...
2
votes
1answer
41 views

Prove that regular languages and context-free languages aren't closed under $Perm(L)$

Let the operation $$Perm(L) = \{ w | \exists u \in L \text{ such that } u \text{ is a permutation of } w \}$$ Prove that both regular languages and CFLs aren't closed under $Perm(L)$. I've tried ...
2
votes
2answers
46 views

Prove/ Disprove: If $L$ is a CFL then $A(L)$ is a CFL too

Consider the operation $A(L)$: $$A(L) = \{ w: w\in L \land w_R \notin L \}$$ where $w_R$ is the reverse of $w$. Prove/ Disprove: if $L$ is a CFL language so does $A(L)$. I am almost certain ...
-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
23 views

Ogden’s lemma on CFG

I'm trying to understand Ogden's lemma, and I know there are 4 cases, but in the next example I can only find 3: Assume A = {$0^n1^m0^k$ | k = $max${n, m}} is CF: Choose z = $0^k1^k0^k ∈ A$, z = ...
5
votes
1answer
87 views

Closure properties of linear context-free languages

Under what operations are linear context-free languages closed? Suppose $L_1, L_2$ are two linear context free languages. Are there any guarantees about $L_1 \cup L_2$, $L_1 \cap L_2$, ...
4
votes
1answer
62 views

Language of walks in a grid – context-free?

Consider the infinite two-dimensional grid with integer co-ordinates. A walk in the grid can be represented by a string over the alphabet $\{u,d,l,r\}$, where the letters stand for moving one square ...
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
votes
1answer
26 views

Eliminate Left Recursion

The part I want to modify: B -> F | B A | A What is the correct way to remove this left recursion? I was thinking ...
2
votes
1answer
38 views

prove that a language is context free given a regular language

R is a regular language over $\Sigma=\{0,1\}$ $Sub(R)=\{0^i1^j \mid \exists w\in R.|w|=i-j \}$ I need to prove that Sub(R) is context free. I know that the quotient of a context free language with a ...
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
63 views

Find a CFG for the language $\{ x\$y \mid x,y\in\{a,b\}^* \wedge |x| \ne |y| \}$?

Consider the language below, on the alphabet $\Sigma = \{a,b,\$\}$: $$L = \left\{ x$y \mid x,y\in\{a,b\}^* \land \left|x\right| \ne \left|y\right| \right\}$$ I need to define a CFG for this language. ...
1
vote
0answers
60 views

What is a good example of an NL-complete context free language?

Setting Exactly as the title stated: Give an example of an $\mathsf{NL}$-complete context free language. $\newcommand{\angle}[1]{\langle #1 \rangle}$ Current Solution Recall in the past we ...
2
votes
2answers
128 views

Context Free Grammar for $a^*b^*c^* - \{a^n b^n c^n \mid n \geq 0 \}$ [duplicate]

I'm having trouble constructing a Context Free Grammar for the following language: $$a^{\ast}b^{\ast}c^{\ast} - \{a^{n} b^{n} c^{n} \mid n \geq 0 \}$$ I believe it's telling me that no string can be ...
2
votes
2answers
40 views

Is the question of whether the language of a DFA/CFG is equal to a particular set of string decidable?

Suppose I have a set of strings $S$ that is generated from the alphabet. Suppose I have a DFA $D$ and a CFG $G$, are the questions of $\{D\mid D\text{ is a DFA and }L(D) = S\}$ and $\{G\mid G\text{ ...
0
votes
1answer
47 views

Confusing example of a language which may be Context-free or not context-free

Hi so consider the language $L= \{(0^i)(1^j)\mid i=k*j \text{ for some positive }k\}$ Could I not rewrite this as $\{((0^k)^j)(b^j)\mid k>1\}$. Seeing it in this form makes me think of a form $a^n ...
2
votes
2answers
42 views

Ambiguous context free

Is there any technique to prove that a given language L is not ambiguous context-free? Here I don't know that whether L is CFL or not.