The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
10
votes
3answers
13k 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 ...
1
vote
2answers
150 views

Generate the word using this grammar

Using this grammar, over the alphabet $\Sigma=\{a\}$ $$ S \rightarrow a \\ S\rightarrow CD \\ C\rightarrow ACB \\ C\rightarrow AB \\ AB\rightarrow aBA \\ Aa\rightarrow aA \\ Ba\rightarrow aB \\ AD\...
1
vote
1answer
212 views

Closure properties of languages

Let $P$ be a regular language and $Q$ be a context-free language such that $Q \subseteq P$(For example, let $P = a^*b^*$ and $Q = \{ a^nb^n | n \ge 0\}$). Then which of the following is always ...
5
votes
1answer
693 views

Deterministic context-free languages are closed under regular right-product

I am looking for a proof for the following problem: For languages $L$ and $R$, if $L$ is deterministic context-free and $R$ is regular, then $LR$ is a deterministic context-free language. Note:...
6
votes
2answers
309 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 ...
8
votes
3answers
11k views

Context-free Languages closed under Reversal

In class this week we've been learning about the CFLs and their closure properties. I've seen proofs for union, intersection and compliment but for reversal my lecturer just said its closed. I wanted ...
2
votes
1answer
164 views

Recursive and regular languages

I'm trying to study for an exam and having difficulty with the following practice questions. Any help would be appreciated. Give a language $L$ such that $L$ is not recursive but $\text{prefix}(L)$ ...
0
votes
1answer
2k views

Is the complement of $ww^R$ context-free?

Identify the language given by $L = \{ x \in (0,1)^* : x \neq ww^R, w \in (0,1)^*\}$. Note: $w^R$ is the reverse of the string $w$. Closure property can/should be applied only in the cases when the ...
3
votes
1answer
2k views

LR(1) - Items, Look Ahead

I am having diffuculties understanding the principle of lookahead in LR(1) - items. How do I compute the lookahead sets ? Say for an example that I have the following grammar: S -> AB A -> aAb | b ...
3
votes
2answers
3k views

CFG and PDA for the grammar that has perfectly nested parentheses and brackets

I gotta make a CFG and PDA for the grammar that has perfectly nested parentheses and brackets. $\qquad\begin{align} S &\to [S] \\ S &\to (S) \\ S &\to SS \\ S &\to \varepsilon \...
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 ...
7
votes
2answers
3k 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 ...
2
votes
2answers
1k views

Recursive-Descent Predictive Parser for $S \rightarrow 0S1\ |\ 01$

I am having difficulty with one of the exercises in the Dragon Book: Exercise 2.4.1(c): Construct recursive-descent parsers, starting with the following grammars: $$S \rightarrow 0S1\ |\ 01$$...
5
votes
1answer
215 views

Hardness of ambiguity/non-ambiguity for context-free grammars

A grammar is ambiguous if at least one of the words in the language it defines can be parsed in more than one way. A simple example of an ambiguous grammar $$ E \rightarrow E+E \ |\ E*E \ |\ 0 \ |\ ...
0
votes
1answer
236 views

Proving the language of words with equal numbers of symbols non-context-free [duplicate]

Possible Duplicate: How to prove that a language is not context-free? I'm having a hard time figuring this out, any help is appreciated. Let EQUAL be the language of all words over $\Sigma = \{...
1
vote
2answers
800 views

Context Free Grammar for language

The language is $L = \{a^{i} b^{j} c^{k} \;|\; k \neq 2j\}$. I'm trying to write a grammar for this language, what I have so far is: $S \rightarrow AT_{1} \;|\; AT_{2} \;|\; AT_{3} \;|\; AB \;|\; AC$ ...
3
votes
4answers
5k views

A context-free grammar for all strings that end in b and have an even number of bs

I'm trying to find CFG's that generate a regular language over the alphabet {a b} I believe I got this one right: All strings that end in b and have an even number of b's in total: $\qquad S \to SS \...
2
votes
1answer
297 views

Designing context free grammar for a language with range restriction on repetition of alphabets

I am having issue with designing contex free grammar for the following language: $L = \{0^n 1^m \, | \, 2n \leq m \leq 3n \}$ I can design for the individual cases i.e. for $m \geq 2n$ and $m \leq ...
1
vote
1answer
148 views

Phrase generators for use with testing grammars that don't use a seed

In helping someone understand phrase generators for use with testing grammars, think compiler test cases, I noted that I have never found a phrase generator that is knowledgeable of the grammar, and ...
2
votes
3answers
2k 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|n,m\in\mathbb N\land n\ge m\}$$ Is my hypothesis true or is ...
4
votes
1answer
480 views

Proof of equivalence of parse-trees and derivations

Intuitively, every derivation in a context-free grammar corresponds to a parse-tree and vise versa. Is this intuition correct? If so how can I formalize and prove such a thing?
9
votes
1answer
1k views

Arithmetic expressions grammar transformation

In the article Parsing Expressions by Recursive Descent by Theodore Norvell (1999) the author starts with the following grammar for arithmetic expressions: ...
3
votes
1answer
195 views

Factor a grammar

Consider the context free grammar: $\qquad \begin{align} \mathrm{bill} &\to \mathrm{items}\ \mathrm{total}\ \mathrm{vat} \\ \mathrm{items} &\to \mathrm{item} \mid \mathrm{item}\ \...
6
votes
1answer
287 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 ...
3
votes
1answer
80 views

Showing $A-B$ is a CFL where $A$ is a CFL and $B$ is finite

Show that if $A$ is a context-free language and $B$ is finite, then $A - B$ is a context-free language. I'm just not sure how to use their properties to formally show this. Thanks for all the help in ...
3
votes
1answer
4k views

Context-free grammar to a pushdown automaton

I'm trying to convert a context free grammar to a pushdown automaton (PDA); I'm not sure how I'm gonna get an answer or show you my progress as it's a diagram... Anyway this is the last problem I have ...
8
votes
1answer
451 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.
2
votes
1answer
892 views

Eliminating useless productions resulting from PDA to CFG converison

In my class we used a Pushdown Automata to Context Free Grammar conversion algorithm that produces a lot extraneous states. For example, for two transitions, I am getting the following productions ...
24
votes
4answers
20k views

How to prove that a grammar is unambiguous?

My problem is how can I prove that a grammar is unambiguous? I have the following grammar: $$S → statement ∣ \mbox{if } expression \mbox{ then } S ∣ \mbox{if } expression \mbox{ then } S \mbox{ else } ...
3
votes
2answers
5k views

Context-free grammar for $\{ a^n b^m a^{n+m} \}$

I've got a problem with this task. I should declare a context-free grammar for this language: $\qquad \displaystyle L := \{\, a^nb^ma^{n+m} : n,m \in \mathbb{N}\,\}$ My idea is: We need a start ...
4
votes
1answer
8k views

Removing Left Recursion from Context-Free Grammars - Ordering of nonterminals

I have recently implemented the Paull's algorithm for removing left-recursion from context-free grammars: Assign an ordering $A_1, \dots, A_n$ to the nonterminals of the grammar. for $i := 1$ ...
9
votes
1answer
611 views

Proof that $\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \}$ is not (co-)recursively enumerable

I would like to use your help with the following problem: $L=\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \}$. Show that $L \notin RE \cup CoRE$. I know that to prove $L\notin RE$, it is enough to find a ...
21
votes
1answer
2k views

Decide whether a context-free languages can be accepted by a deterministic pushdown automaton

Given a context-free grammar G, there exists a Nondeterministic Pushdown Automaton N that accepts exactly the language G accepts. (and visa versa) There may also exist a Deterministic Pushdown ...
7
votes
1answer
7k 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) ...
1
vote
3answers
354 views

Use closure properties to transform languages to $L := \{ a^nb^n : n\in \mathbb N \}$

For the purpose of proving that they are not regular, what closure properties can I use to transform the languages $L_a = \{ a^*cw \mid w \in \{a,b \}^* \land |w|_a = |w|_b \}$ and $L_b = \{ab^{i_1}...
9
votes
3answers
2k views

If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?

I'm am stuck solving the next exercise: Argue that if $L$ is context-free and $R$ is regular, then $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} $ (i.e. the right quotient) is context-...
4
votes
1answer
571 views

A context free grammar proof

There is a problem which I cannot solve. If you give a tip I will be very glad. Prove that following language is not context free: $L= \{ a^nb^m | \gcd(n,m) = 1 \}$. It can be proven using the ...
5
votes
1answer
355 views

The operator $A(L)= \{w \mid ww \in L\}$

Consider the operator $A(L)= \{w \mid ww \in L\}$. Apparently, the class of context free languages is not closed against $A$. Still, after a lot of thinking, I can't find any CFL for which $A(L)$ ...
6
votes
4answers
375 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 ...
5
votes
2answers
339 views

Is $A=\{ w \in \{a,b,c\}^* \mid \#_a(w)+ 2\#_b(w) = 3\#_c(w)\}$ a CFG?

I wonder whether the following language is a context free language: $$A = \{w \in \{a,b,c\}^* \mid \#_a(w) + 2\#_b(w) = 3\#c(w)\}$$ where $\#_x(w)$ is the number of occurrences of $x$ in $w$. I can't ...
5
votes
1answer
278 views

Closure against the operator $A(L)=\{ww^Rw \mid w \in L \wedge |w| \lt 2007\}$

I would like your help with the following question: Let $L$ be a language, and operator $A(L)=\{\,ww^Rw \mid w \in L\ \wedge\ |w| \lt 2007\,\}$ where $x^R$ is the reversed string of $x$. Which of ...
5
votes
1answer
980 views

Chomsky normal form and regular languages

I'd love your help with the following question: Let $G$ be context free grammar in the Chomksy normal form with $k$ variables. Is the language $B = \{ w \in L(G) : |w| >2^k \}$ regular ? ...
4
votes
4answers
4k 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 ...
14
votes
2answers
998 views

Are the Before and After sets for context-free grammars always context-free?

Let $G$ be a context-free grammar. A string of terminals and nonterminals of $G$ is said to be a sentential form of $G$ if you can obtain it by applying productions of $G$ zero or more times to the ...
4
votes
3answers
184 views

Language of the graph of an affine function

Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let : be a symbol distinct from any digit. Let $a$ and $b$ ...
10
votes
5answers
1k views

Language of the values of an affine function

Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let $a$ and $b$ be integers, with $a > 0$. Consider the language of the decimal expansions ...
16
votes
2answers
2k views

Decidablity of Languages of Grammars and Automata

Note this is a question related to study in a CS course at a university, it is NOT homework and can be found here under Fall 2011 exam2. Here are the two questions I'm looking at from a past exam. ...
11
votes
2answers
4k views

How can I prove this language is not context-free?

I have the following language $\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$ I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a context-...
10
votes
1answer
384 views

Given a string and a CFG, what characters can follow the string (in the sentential forms of the CFG)?

Let $\Sigma$ be the set of terminal and $N$ the set of non-terminal symbols of some context-free grammar $G$. Say I have a string $a \in (\Sigma \cup N)^+$ such that $x a y \in \mathcal{S}(G)$ where $...
12
votes
2answers
9k views

Are all context-free and regular languages efficiently decidable?

I came across this figure which shows that context-free and regular languages are (proper) subsets of efficient problems (supposedly $\mathrm{P}$). I perfectly understand that efficient problems are a ...