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
9
votes
1answer
139 views

Does the following transformation preserve context-freeness?

I encountered this problem involving manipulating a context-free language. Let $L$ be a context-free language. Define $L^{\#} = \{ x : x^i \in L$ for every $i=0,1,2,...\}$. Is $L^{\#}$ always context-...
9
votes
1answer
24k 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 ...
8
votes
2answers
2k 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 ...
8
votes
2answers
58k views

Different between left-most and right-most derivation [duplicate]

I am a beginner started learning theoretical computer science. I just came through context-free grammars. So my question is: what is the different between left-most and right-most derivation? ...
8
votes
2answers
291 views

Is {a^n (a+b)^n | n>0} a Deterministic CFL?

$L = \{ a^n (a+b)^n | n>0\}$ A book I'm reading says it is, but considering we can't know where the second part gonna start, and it might start with a as well, then how can we accept this using ...
8
votes
2answers
662 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 ...
8
votes
4answers
2k views

Where do the length restrictions of the pumping lemma come from?

For a language $L$ with pumping length $p$, and a string $s\in L$, the pumping lemmas are as follows: Regular version: If $|s| \geq p$, then $s$ can be written as $xyz$, satisfying the following ...
8
votes
1answer
3k views

Are DCFLs closed under reversal?

According to this chart, DCFLs are closed under reversal. However, I am not convinced as the intuitive proof (reversing the arrows of the controlling finite state machine and switching the pushes and ...
8
votes
1answer
486 views

Is this language Context-Free?

Is the language $$L = \{a,b\}^* \setminus \{(a^nb^n)^n\mid n \geq1 \}$$ context-free? I believe that the answer is that it is not a CFL, but I can't prove it by Ogden's lemma or Pumping lemma.
8
votes
1answer
598 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 ...
7
votes
2answers
730 views

Parikh's Theorem: CFL's “contain” regular languages?

The first sentence of the Wikipedia article for Parikh's Theorem states: "Parikh's theorem in theoretical computer science says that if one looks only at the relative number of occurrences of ...
7
votes
2answers
4k views

Inherent ambiguity of the language $L_2 = \{a^nb^mc^m \;|\; m,n \geq 1\}\cup \{a^nb^nc^m \;|\; m,n \geq 1\}$

I went through a question asking me to choose the inherently ambiguous language among a set of options. $$L_1 = \{a^nb^mc^md^n \;|\; m,n \geq 1\}\cup \{a^nb^nc^md^m \;|\; m,n \geq 1\}$$ $$and$$ $$L_2 ...
7
votes
3answers
17k views

Regular Expression to Context-Free Grammar

Anyone knows if there is an algorithm for directly write the context-free grammar that generates a given regular expression?
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 ...
7
votes
1answer
8k views

Relation between simple and regular grammars

I am reading "An Introduction to Formal Languages and Automata" written by Peter Linz and after reading the first five chapters I face below problem with simple and regular (especially right linear) ...
7
votes
2answers
5k views

Converting to CFG from a CFL? [duplicate]

I am trying to learn CFG. Now to make a CFG from a CFL it is really difficult for me. Is there any simple rule or steps so that I can easily find a CFG for a CFL. I am trying to solve one problem ...
7
votes
1answer
182 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 ...
7
votes
1answer
572 views

Are these valid counterexamples to proofs for CF languages with Non-CF complements?

Someone asked for examples of context-free languages with non-context-free complements. The first answer says: The language $L_1= \{ww \mid w \in \{a,b\}^*\}$ is not context-free (as can be shown ...
7
votes
1answer
741 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 ...
7
votes
1answer
358 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
2answers
13k views

Context Free Grammar for {a^ib^j | i,j ≥ 0; i ≠ 2j}

Can someone help with this: $L=\{a^ib^j \mid i,j \ge 0 \text{ and } i \ne 2j\}$ I'm trying to write a grammar for this language? I don't know how to do this. I tried this: $S \rightarrow aaAb \...
7
votes
1answer
641 views

Convert PEG to BNF

Parsing expression grammars (PEGs) are unambiguous and have a superficially similar syntax to BNF, but include three important differences: The ordered choice operator ...
7
votes
1answer
174 views

Context-free languages not closed under making them “extension-free”

For a language $L$, define: $$ NE(L) = \{x \in L : x \text{ is not the proper prefix of any string in } L\} $$ I'm trying to show context-free languages are not closed under this operation. I've been ...
7
votes
2answers
810 views

Generating a set of minimal-length strings that, together, invoke every production of a context free language

Problem (tl;dr) Given a context free grammar, $G$, find a set of strings that take $G$ through every production it has at least once. How and how fast can it be done? Background I'm working on a ...
7
votes
1answer
2k 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 ...
7
votes
1answer
1k views

Techniques to prove a language is not DCFL

I know that DCFL is closed under complementation and intersection with regular languages. By using these we can prove that a language is not DCFL. Are there any other techniques that will help me to ...
7
votes
1answer
595 views

How to convert a non-embedding context free grammar to regular grammar?

Please note that I am aware the undecidability of the conversion of context-free grammar to regular grammar. But given the non-embedding property of the input context-free grammar, is there any ...
7
votes
1answer
86 views

Are there any context-free languages that are not known to be in $\mathrm{DTIME}(O(n))$?

The problem of determining, given a string $x$ and a context-free grammar $G$, whether $x \in L(G)$ is conjectured to take more than linear time in the length of $x$. Currently the best known ...
7
votes
2answers
1k views

DCFL with prefix property have LR(0) grammar?

There are two important theorems about LR(k) grammars and DCFL. Mentioned here. A language has an LR(1) grammar iff it is DCFL. A language has an LR(0) grammar iff it is DCFL and has prefix property. ...
7
votes
3answers
4k views

Proving that any CF language over a 1 letter alphabet is regular

I would like to prove that any context free language over a 1 letter alphabet is regular. I understand there is Parikh's theorem but I want to prove this using the work I have done so far: Let $L$ be ...
7
votes
1answer
784 views

Can this CFG be written into an equivalent LL(1) grammar?

I have the following CFG which I suspect cannot be rewritten to one which is LL(1): $S \rightarrow \epsilon\ |\ aSbS\ |\ bSaS\ |\ cSdS\ |\ dScS$ I've thought about it for a while, and can't seem to ...
6
votes
3answers
2k views

Context-free grammar for $L = \{a^{2^k}, k \in\mathbb{N}\}$

In an exercise, I am asked to find a context free grammar for language $L = \{a^{2^k}, k \in \mathbb{N}\}$. I have been trying to use a "doubling" variable. If $a^{2n} \in L, n\in\mathbb{N}$ then use ...
6
votes
2answers
7k 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 ...
6
votes
4answers
401 views

Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?

How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language. $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$, where $x^R$ is the ...
6
votes
2answers
8k views

Why are CFLs not closed under intersection?

I'm struggling with understanding how context free languages can be closed under union but are not closed under intersection. I was wondering if there was a simple proof or example demonstrating that ...
6
votes
2answers
772 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 ...
6
votes
2answers
100 views

Can the regular image of a context-free language be undecidable?

I just need to know the truth or falsity of a simple statement. Let $L_1$ be a context-free language over an alphabet which contains some number of characters $\Sigma$, as well as a single, special ...
6
votes
2answers
3k views

In context-free grammar (CFG), what is the importance of doing both leftmost and rightmost derivations?

I am a beginner learning theoretical computer science. While learning about CFG, I found that doing both leftmost and rightmost derivations gave me the same parse tree. So, my question is: Why is it ...
6
votes
1answer
279 views

Are these special (one production) Context-Free Grammars always unambiguous?

Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production): $S \rightarrow aSb\;|\;\epsilon$ $S \rightarrow aSbS\;|\;\epsilon$ $S \rightarrow ...
6
votes
4answers
139 views

Minimal size of a context-free grammar which defines $L_n=\{a^k\mid 1\le k\le n\}$

I am looking for the minimal size of a context-free grammar which defines the finite language $$L_n=\{a^k\mid 1\le k\le n\}.$$ The size of a grammar is defined as the total length of all right-hand ...
6
votes
2answers
3k views

Is Python a context-free language?

From Wikipedia: Off-side_rule#Implementation, there is a statement: ...This requires that the lexer hold state, namely the current indentation level, and thus can detect changes in indentation ...
6
votes
1answer
1k 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$, $\overline{L_1}...
6
votes
1answer
1k views

Check for balanced parentheses in an expression in log-space

Given an expression (a word in the one-sided Dyck language), I want to write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in the expression. For ...
6
votes
3answers
207 views

First half of context-free palindromes

If $L\subseteq\Sigma^*$ is a regular language, then $\text{mir}(L) = \{ww^R \mid w\in L\}$ is context-free. This is a nice exercise. Question: does the reverse hold? Thus, if $\text{mir}(L)$ is ...
6
votes
3answers
232 views

Prove that the complements of pumping-style languages are context-free

Define $L = L(u,v,x,y,z) = \{uv^ixy^iz : i \geq 0\}$, with $u,v,x,y,z \in \Sigma^*$. Prove that $\overline{L}$ is a CFL for all $u, v, x, y, z$ Clearly, $L$ is a CFL, as it is generated by the ...
6
votes
2answers
321 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 ...
6
votes
1answer
343 views

Determining whether a CFG is $LL(k)$ for any $k$?

In Knuth's original paper on $LR(k)$ grammars, he proved that the decision problem "Given a CFG $G$, is there a $k$ such that $G$ is an $LR(k)$ grammar?" is undecidable. Is there a similar result ...
6
votes
1answer
448 views

Prove that the class of CFG languages that are closed under reversal is undecidable

Note The wording of the title may be a bit vague, but I'm not asking if CFLs are closed under reversal. Please see below. Problem Description Given a word $w$, define $w^{r}$ to be its reversal. ...
6
votes
2answers
291 views

Prove that context free languages aren't closed under DropMiddle

The question is simple: $\qquad \operatorname{DropMiddle}(L)=\{xy\in\Sigma^* \mid |x|=|y| \land \exists a\in\Sigma\colon xay\in L\}$. Prove that CFL's aren't closed under $\operatorname{DropMiddle}$. ...
6
votes
2answers
5k views

Examples of Context Free Languages

I'm having a hard time thinking of context free languages. The only example I've been able to think of is $0^n1^n$, but I'm having a hard time thinking of any others. Can I get some examples?

1
2
3 4 5
26