Questions tagged [context-free]

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

Filter by
Sorted by
Tagged with
13
votes
2answers
13k views

Is the complement of { ww | … } context-free?

Define the language $L$ as $L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$. In other words, $L$ contains the words that cannot be expressed as some word repeated twice. Is $L$ context-free or not? I'...
3
votes
1answer
113 views

Looking for a contex-free grammar for the following language

I want to derive a context free grammar for the following language on alphabet $\Sigma=\{a,b\}$: $\qquad\displaystyle \{ xax'yby'z \mid x,y,z\in\Sigma ^*, |x|=|x'|, |y|=|y'|, |z|=|x|+|y|\}$ I am ...
1
vote
2answers
192 views

Uncertainty whether $\{a^i b^j c^k \mid i+j \le k\}$ is context-free or not

I'm having trouble with this particular language: $$\{a^i b^j c^k \mid i+j \le k\}$$ If it's not context-free, I don't know how to correctly apply the Pumping Lemma for CFLs; if it is context-free, I ...
1
vote
1answer
382 views

Binary operators with higher precedence than unary operators

Generally (perhaps always) in programming languages, unary operators have the highest precedence. In some langauges, such as Standard ML, one can dynamically change the precedence of binary operators ...
-1
votes
1answer
236 views

Relative complement of a Non CFL to CFL

Let $L$ be a given Context Free Language over the alphabet $\{a,b\}$. Now consider $$L_1=L-\{xyx\ |\ x,y\in\{a,b\}^*\}$$ I know that $\{xyx\ |\ x,y\in\{a,b\}^*\}$ is not Context Free (by using pumping ...
2
votes
1answer
274 views

Is the language of all ucv with u ≠ v context-free?

Is $L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^* , w_1 \neq w_2 \}$ a CFL? In my opinion it is not since if we want to know the inequality of $w_1$ and $w_2$ we must be aware of their equality and that is ...
15
votes
1answer
20k views

Intersection of context free with regular languages

The intersection of a context free language L with a regular language M, is said to be always context free. I understood the cross product construction proof, but I still don't get why it is context ...
3
votes
2answers
142 views

What does the symbol # mean when it comes to languages

Given the following: $$\{ w\#x \mid w^R \text{ is a substring of $x$, with $x$ and $w \in \Sigma^*$} \}$$ What does $w\#x$ denote?
1
vote
2answers
196 views

Why is this not a regular language

So I recently had a problem where I had to create a regular language. After consulting my professor on my solution he told me it was close to correct but to check my definition of a regular language. ...
11
votes
2answers
13k views

Examples of context-free languages with a non-context-free complements

Context-free languages are not closed under complementation. In the lectures we have been given the same argument as here on Wikipedia: For $$A = \{\mathtt a^n \mathtt b^n \mathtt c^m;~m, n ∈ ℕ_0\}\...
26
votes
2answers
24k views

How to prove that a language is context-free?

There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free? What techniques are there to prove this? Obviously, one way is to exhibit ...
2
votes
2answers
160 views

Is the language with decreasing numbers of a, b and c context-free by pumping lemma?

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)^*, n_a(...
-2
votes
2answers
124 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
769 views

Showing Context Free Grammars that are regular if and only if L(G) = Σ∗.

Suppose that G is a context-free grammar. How can I show that “Is L(G) regular?” is undecidable. Also, prove that L is always context-free but is regular if and only if L(G) = Σ∗. This is what I ...
0
votes
1answer
273 views

Context free language and the complement of it

Given the language $L_1 = \{a^i b^j c^k \mid i \neq j \vee i \neq k\}$, I need to determine whether it is context-free by using the pumping lemma. I must do the same for the complement of this ...
1
vote
1answer
606 views

Converting to Chomsky normal form

Im having some problems with a qeuestion regarding converting a context free grammar to chomsky normal form. I have S -> abC | babS | de C -> aCa |b I know what to do with the case ...
-1
votes
1answer
132 views

Context-free Language: deciding z string

Let $L = \{ x \in \{a,b\}* | \ |x|_a \leq |x|_b^2\}$ I know this is a NOT context free language. How can i choose the correct $z=uvwxy$ and try to apply the Pumping Lemma? I think that $z=(a^n b)^...
1
vote
1answer
118 views

Using pumping lemma to prove a language is not context free

When using the pumping lemma for a context free language, if I write any $w \in L$ as $uvxyz$, is my goal to show that a string will not pump for ANY arrangement of $uvxyz$ that I choose, or is my ...
1
vote
1answer
3k views

How does the kleene star and union work in a context free grammar?

Im in a functional languages computer science class and I have a question on the use of the kleene star and the Union in a context free grammar. for the kleene star I have an idea of how I might do ...
1
vote
2answers
3k views

CFG for $\{a^ib^jc^k \mid i \neq j+k\}$

I am trying to design a context-free grammar for the language $L = \{a^ib^jc^k \mid i\neq j+k\}$ over the alphabet $\Sigma = \{a,b,c\}$. I know that I can split this up into the union of two cfg's $...
1
vote
1answer
1k views

Rules regarding Chomsky Normal Form (CNF) grammars

I'm writing a context-free grammar that I hope will be in Chomsky Normal Form, and I have two questions: Can I use a single variable (a non-terminal) on the left-hand side of multiple rules? Can I ...
1
vote
0answers
96 views

Can regular expression captures be matched by a CFG being simulated by an $LR(k)$ parser?

I have seen this question: Are regular expressions $LR(k)$? and my question is slightly related. Suppose I have a regular expression: RE=(aa)?(aa) and I convert it to a grammar: G ::= A B A ::= C | (...
18
votes
3answers
1k views

Algorithm to test whether a language is context-free

Is there an algorithm/systematic procedure to test whether a language is context-free? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \...
2
votes
2answers
93 views

Can the String, $0^p 0^p 0^p$, be Used with the Pumping Lemma to Show that $w^r w w^r$ is Not Context Free?

I'm trying to show that $L=\left\{w^rww^r:w \in \{0,1\}^*\right\}$ is not context free using the pumping lemma. I thought picking the string, $0^p0^p0^p$, would be a good candidate for this, but ...
0
votes
1answer
305 views

conversion of this grammar to CNF

My task is to convert the following grammar to CNF: $S \to SS \mid (S) \mid \lambda$ after removing lambda productions: $S\to SS, S\to (S), S\to(), S\to S$ after removing unit productions: $S\to ...
0
votes
1answer
2k views

Is my proof for a context free language correct? Same number of a's as b's

I have the following grammar G: $$ \begin{align*} &S \to aB|bA \\ &A \to a|aS|bAA \\ &B \to b|bS|aBB \end{align*} $$ I am going to prove that this language L(G) consists of words with the ...
1
vote
1answer
5k views

Pushdown automaton for complement of { ww | … }

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
993 views

Constructing Context Free Grammar [duplicate]

I am stuck and having a hard time with this question. I want to construct a CFG for the language $$L = \{{a^lb^mc^n | l,m\in N, n=|l-m|\}}$$ I know that the language consists of strings where: 1. ...
-1
votes
1answer
1k views

Determining whether a context-free language (CFL) described by a given grammar is regular (RL)

In my homework we're given the following problem: Determine whether the context-free language described by the following grammar is regular, showing all the reasoning steps: S -> T T | U T -> 0 T | ...
4
votes
4answers
3k views

What information do we get from a compiler's parse tree?

In the compiler course by Alex Aiken on Coursera, more specifically lecture 05-02 Context Free Grammars, the professor says that CFGs give answers of the type yes/no, i.e. whether the given string of ...
3
votes
5answers
14k views

Context-free grammar for language with unequal numbers of a and b

I've been trying to get a CFG for the language of all words with unequal numbers of a and b, i.e. $$\{u \in \{a, b\}^* \mid \text{number of occurrences of $a$ and $b$ in $u$ are unequal} \},$$ but ...
4
votes
3answers
236 views

Designing a CFG that produces as many c's as the difference of numbers of a's and b's

The question is to design a CFG for the language of words that have as many c's as the difference of numbers of a's and b's, that is $\qquad\displaystyle L = \{(a^l)(b^m)(c^n) \mid l, m \in \mathbb{N}...
4
votes
1answer
1k views

Does Reverse Polish Notation have an LL grammar?

Let L be the language of all arithmetic expressions written in Reverse Polish Notation, containing only binary operators. $\Sigma(L) = \{n, o\}$, n := number, o := operator. Is there an LL grammar G ...
1
vote
2answers
90 views

Grammar generating specific language

Construct a context-sensitive grammar that generates L: L = {a^n b^m c^k|k>n, k>m} I believe my productions should go along this lines: ...
1
vote
1answer
55 views

Which grammar is this?

Having the grammar G = (V,P,S) with variable V = {S,A} over the alphabet {a,b} with the ...
7
votes
1answer
1k views

Is the Syntax of C Language completely defined by CFGs?

I think the Question is self sufficient. Is the syntax of C Language completely defined through Context Free Grammars or do we have Language Constructs which may require non-Context Free definitions ...
2
votes
2answers
232 views

What does this context-free grammar generate?

The grammar is $$ S\to aSb\ |\ bSa\ |\ SS\ |\ \epsilon. $$ I think this generates the set of strings with equal numbers of $a$'s and $b$'s based on examples I've done. Is this correct?
0
votes
3answers
2k views

How to prove every context-free language over a unary alphabet is regular?

How can I show that every context-free language over a unary alphabet is regular?
0
votes
2answers
512 views

The complement of $\{w: w\text{ has equal numbers of $a$'s, $b$s' and $c$'s}\}$ is context-free

Let $L$ be the language $\{w \mid w \text{ has equal numbers of \(a\)'s, \(b\)'s and \(c\)'s}\}$. Prove that its complement $\overline{L}$ is context free.
1
vote
1answer
2k 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 = \...
0
votes
1answer
73 views

Deciding the class of certain languages [closed]

I am preparing for my exam in Formal languages and Automata theory and I'm looking at some old exam questions right now. I need help with the following question: For each of the following ...
3
votes
2answers
94 views

Is $\{s_0 w s_1 : s_0s_1\in L_1, w\in L_2 \}$ context free if $L_1$ and $L_2$ are?

In class, it was alluded to that a language: \begin{equation*} \{s_0 w s_1 : s_0s_1\in L_1, w\in L_2 \} \end{equation*} would be context free, if $L_1$ and $L_2$ are context free. Intuitively, that ...
1
vote
1answer
610 views

Non context free language that is pumpable? [duplicate]

For my homework assignment, I have to come up with a non-cfl that is pumpable. I came up with the following: $$ C = \{a^n b^n c^n d^m \mid n \ge 1 \text{ and } m \ge 1 \} $$ I'm not sure whether ...
3
votes
1answer
2k views

why does ${a^nb^n}$ fit the pumping lemma for context-free languages?

I am writing somthing about Ppumping Lemma. I know that the language $L = \{ a^nb^n| n ≥ 0 \}$ is context-free. But I don't understand how this language satisfies the conditions of pumping lemma (for ...
2
votes
2answers
2k views

Context Free Grammar for $\{0^n1^n \mid n \geq 0\}^*$

Give a context free grammar for the following language over $\Sigma = \{0,1\}$: $ L = L_1^* $ where $ L_1 = \{0^n1^n : n \geq 0\}$. Not really sure where to start with this one. Any help is ...
2
votes
1answer
633 views

Would it be possible that the intersection of two non-context-free languages is context-free?

Assume two languages $L_1$ and $L_2$, both of which are non-context-free. Let $L = L_1 \cap L_2$. Could $L$ be context-free?
1
vote
1answer
1k views

Derive a Context Free Grammar from a language

I am having challenges (in two phases) with creating a CFG. Derive the CFG for the following language Show parse trees for the strings cacab and aacabbb obtained from the grammar designed above. I ...
13
votes
5answers
4k views

How is non-ambuiguity different from determinism?

I am trying to understand what is meant by "deterministic" in expressions such as "deterministic context-free grammar". (There are more deterministic "things" in this field). I would appreciate an ...
0
votes
2answers
664 views

Prove L to not context free using pumping lemma on language L

$L = \{0^i1^j0^i1^j|i,j \geq 0\}$ I've tried letting $s = 0^p1^p0^p1^p$. But not sure where to go from here. Help would be appreciated.
5
votes
3answers
10k views

Language of balanced parentheses; Biconditional proof about parentheses

Let L be language of balanced parentheses. (a) Prove If there are equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'s, then w is in L. (b) Prove If w is in L, then ...