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
4
votes
4answers
6k views

Prime number CFG and Pumping Lemma

So I have a problem that I'm looking over for an exam that is coming up in my Theory of Computation class. I've had a lot of problems with the pumping lemma, so I was wondering if I might be able to ...
3
votes
1answer
4k views

unambiguous grammar but it's not LR(1)

I have following grammar: $$A \to a A a \mid \varepsilon$$ This grammar is not ambiguous because it has no more than one parse tree from the any sentence generated by this grammar, but there is a ...
1
vote
1answer
714 views

Pumping lemma for Context-Free Languages

I have a question about a specific pumping lemma problem for Context-Free Languages. Suppose we have the following Language: $L = \{a^{i}b^{j}c^{k}d^{l} \mid 0 < i < k \wedge j > l > 0 ...
9
votes
2answers
9k views

Is it decidable whether a given context free grammar generates an infinite number of strings?

Is the decision problem "Does a given context free grammar generate an infinite number of strings" decidable? In order to test whether a context free grammar generates an infinite number of strings or ...
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 ...
6
votes
2answers
900 views

Does there exist context-free grammar with words of length n^2 or n^3?

Does there exist context-free grammar with words of length $n^2$ or $n^3$? I can't see any, we can produce all grammar with words of length $n$ ($S \to Se$), but then it seems to be impossible to ...
3
votes
1answer
2k views

Are permutations of context-free languages context-free?

Given a context-free language $L$, define the language $p(L)$ as containing all permutations of strings in $L$ (i.e. all strings in $L$ such that the order of symbols is not important). Is $p(L)$ ...
3
votes
2answers
3k views

Why are palindrome and not-palindrome both context-free?

Both palindrome and its complement are context-free. This is very interesting. Both are non-deterministic context-free, which in general are not closed under complement. What is it about these two ...
3
votes
3answers
13k 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 ...
3
votes
1answer
1k 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, ...
2
votes
1answer
1k views

every DCFL has an LR(1), an LALR(1) and even an SLR(1) grammar

Here is one discussion that says, "every DCFL has an LR(1), an LALR(1) and even an SLR(1) grammar." And wiki says, "a language can be generated by an LR(k) grammar if and only if it is ...
1
vote
1answer
965 views

Context free grammar for $bin(n)bin(n+1)^R$

It is pretty hard for me to understand, how binary representation of number may be context free. This language $L=\{bin(n)bin(n+1)^R : n \geq 0\}$ is context free. Here, at 1.b, is a PDA which ...
1
vote
1answer
3k views

Is Context Free Language closed under perfect shuffle?

Note that this is not shuffle but perfect shuffle, defined as follows: Let $w = a_{1}a_{2} \ldots a_{n}$ and $x = b_{1}b_{2} \ldots b_{n}$ be two strings of the same length. Then the perfect shuffle ...
13
votes
1answer
6k views

Is there a context free, non-regular language $L$, for which $L^*$ is regular?

I know that there are non-regular languages, so that $L^*$ is regular, but all examples I can find are context-sensitive but not context free. In case there are none how do you prove it?
10
votes
1answer
454 views

Constructing all context-free languages from a set of base languages and closure properties?

One way of looking at regular expressions is as a constructive proof of the following fact: it's possible to construct the regular languages by starting with a small set of languages and combining ...
9
votes
1answer
505 views

How powerful are CFGs that allow an infinite number of rules?

I was wondering recently what would happen if we'd allow context-free grammars to have an infinite number of rules. Clearly, if we'd allow arbitrary such infinite sets of rules, every language $L$ ...
8
votes
1answer
408 views

If L is context-free, must FH(L) be context-free?

Define $FH(L) = \{x \in \Sigma^* : \exists y \in \Sigma^* \text{ with } |x| = |y| \text{ such that } xy \in L\}$. In other words, $FH(L)$ is the set of first halves of even length strings in $L$. ...
7
votes
1answer
111 views

When is ε-removal from a CFG idempotent?

For which context-free grammars is it idempotent to remove $\varepsilon$-productions? Given that there are multiple rewriting algorithms which preserve language and leave the grammar without $\...
7
votes
1answer
189 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 ...
6
votes
2answers
329 views

Grammatical characterization of deterministic context-free languages

Deterministic context-free languages are commonly defined using an automaton concept, the (restricted, deterministic) pushdown automaton. To some that is confusing, as the name context-free refers to ...
5
votes
1answer
613 views

Undecidable problem intersection of two DCFL languages is DCFL?

We have two deterministic pushdown automatas A and B, which languages are deterministic context-free. The problem is to decide if there exists a deterministic pushdown automata, which language is an ...
4
votes
1answer
978 views

How to find First in a left recursive grammar?

One of the basic requirements for a grammar to be LL(1) is : For every pai r of productions A -> X | Y, First(X) and First(Y) should be disjointed. If a grammar is left-recursive, then the set of ...
4
votes
3answers
5k views

Is the language that accepts strings concatenated with their reverse regular?

If the set of regular languages is closed under the concatenation operation and is also closed under the reverse operation ($x^R$ is the reverse of $x$) then is the language generated by $$\{ww^R|w\in\...
3
votes
1answer
558 views

CFG Equivalent of regular expressions

So I was wondering something about the Chomsky hierarchy. DFAs (and NFAs) accept regular languages, while NPDAs accept context-free languages. Right-regular or left-regular grammars produce regular ...
3
votes
2answers
2k views

Prove that the equal-length concatenation of regular languages is context free

If A and B are regular, then prove that $A@B = \{xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y|\}$ is always context free. So I'm trying to come up with the proof that looks something like ...
3
votes
3answers
3k views

Is this language LL(1) parseable?

I tried to find a simple example for a language that is not parseable with an LL(1) parser. I finally found this language. $$L=\{\,a^nb^m\mid n,m\in\mathbb N,\>n\ge m\,\}$$ Is my hypothesis true ...
3
votes
2answers
387 views

Is $L=\{ xyx^Ry^R \mid x,y \text{ is an element of }\{0,1\}^*\}$ context-free?

Is the language $L=\{ xyx^Ry^R \mid x,y \text{ is an element of }\{0,1\}^*\}$ context-free? Note: $x^R$ is the reverse of $x$. My Work: I think this is a context free language. Since a pushdown ...
2
votes
1answer
143 views

Is the language of words with as many a's in the first as b's in the second part context-free?

Is $L = \{ W_1W_2 \mid W_1,W_2 \in (a+b)^* , N_a(W_1) = N_b(W_2)\}$ context free? Can we construct an NPDA for the language? There is a book here that claims $L$ is not CF (without any elaboration), ...
2
votes
2answers
454 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.
2
votes
1answer
88 views

Lower bound for number of nonterminals in a CFG

Let's say we have a context-free grammar for the language $a\mbox{*}b\mbox{*}c\mbox{*}$. Is there a way to determine a lower bound for the number of nonterminals in this grammar? I'm pretty sure you ...
2
votes
2answers
256 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 + ...
2
votes
0answers
2k views

Converting Chomsky Normal Forms to Greibach Normal Form

Here is a passage from Kozen's Automata and Computability (pages 145-146) that I'm confused about: Now we show how to convert an arbitrary grammar to an equivalent one (except possibly for $ \...
2
votes
2answers
6k views

How to show that given language is unambiguous

Given following grammar: $$ \begin{align} S \rightarrow &A1B \\ A \rightarrow & 0A \mid \varepsilon \\ B \rightarrow & 0B \mid 1B \mid \varepsilon \\ \end{align} $$ How can I show that ...
2
votes
1answer
567 views

How to use a CFG to restrict a subset of a*b*c*d* so that there are at most as many a's and b's as d's?

Give Context-free Grammar for the language $\{a^i b^j c^k d^h \mid i,j,h \ge 0, k>0, i+j \le h\}$ This is a training exercise, for which we don't get any answers, in a course I'm taking. I have ...
2
votes
1answer
441 views

Is converting an ambiguous grammar to an unambiguous grammar computable?

Is the problem of converting ambiguous grammar into unambiguous grammar computable? (Consider Domain as all context free languages).
2
votes
1answer
1k views

Can the common algorithm to convert to Chomsky Normal Form result in “useless” productions?

I have an example below which seems to lead to a “useless” production. This is the original grammar: \begin{align*} S&\longrightarrow aX\,|\,Yb\\ X&\longrightarrow S\,...
1
vote
1answer
284 views

CFG problem solved with PDA - looking for alternative solution

I'm trying to find CFG for the language $$L = \{ a^nb^mc^kd^l | n + k = m + l, (n,m,k,l) \in \mathbb{N} \}$$ and what I have done so far is to make PDA which simply does the following: If on the ...
1
vote
2answers
48 views

PDA accepting all words not of the form $b^na^n$

I am studying Automata theory. DFAs and NFAs seem pretty straightforward to me, but I don't quite understand how to design push-down automata for context-free languages. If I have context-free ...
1
vote
1answer
474 views

How can I show context free grammars are strictly more expressive than regular expressions with an example?

I need to show a CFG can express everything that can be expressed by a regular expression, and something that cannot.. I have no idea what example is traditionally used for this.
1
vote
2answers
2k 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 ...
1
vote
2answers
153 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
vote
1answer
156 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
2answers
206 views

Develop the context free grammar to match this language (puzzle)

This is a puzzle type question which asks to create a context-free grammar to match this language: ...
1
vote
1answer
739 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 ...
0
votes
0answers
4k 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
384 views

Prove $ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ is regular or context-free or neither

$ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ Exercises: If the language L is regular (build a DFA or regular expression) else if the language L is context-...
0
votes
1answer
166 views

Context Free Grammar Exercise

I'm studying Context free Grammar and I have a question to a specific Exercise: Why is i. True? How is this possible?
0
votes
2answers
874 views

Context free grammar problem for number of a's is twice the number of b's

Can you to find for me a context free grammar for the following language? $$\{w\in\{a,b\}^*: \#_a(w)=2\#_b(w)\} $$ Here $\#_a(w)$ counts the number of $a$'s in $w$.
-3
votes
2answers
176 views

Grammar for a language with 1/3 of a's

I have this language: $$ L = \left\{ w \in \{a,b,c\}^* \;\big|\; |w| / |w|_a = 3 \right\} $$ where $|w|_a$ is the number of occurrences of $a$. How can I find a grammar that generates it?
12
votes
3answers
19k views

What is complement of Context-free languages?

I need to know what class of CFL is closed under i.e. what set is complement of CFL. I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I ...