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

learn more… | top users | synonyms

1
vote
3answers
70 views

Unable to understand an inequality in an application of the pumping lemma for context-free languages

The problem Prove that the language $\qquad L = \{a^n b^j \mid n = j^2\}$ is not context free using pumping lemma. Approach taken by the book To prove such statements, the book takes the ...
-3
votes
1answer
34 views

Find an unambiguous grammar [on hold]

S → aS | aSbS | (empty) where the alphabet is {a,b} in other words, the set of strings where any prefix has at least as many 'a's as 'b's.
4
votes
2answers
35 views

Incorporating newline-as-statement-terminator heuristics into context-free languages

Several block structured languages (Scala, Go, Ruby, Julia, Quorum, ...) use semicolons as statement terminators, but allow newlines instead of semicolons under certain circumstances. My question is: ...
1
vote
2answers
57 views

Can an intersection of two context-free languages be an undecidable language?

I'm trying to prove that $\exists L_1, L_2 : L_1$ and $L_2$ are context-free languages $\land\;L_1 \cap L_2 = L_3$ is an undecidable language. I know that context-free languages are not closed ...
7
votes
2answers
139 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 ...
-3
votes
0answers
33 views

Are context-free languages ​​complement? [duplicate]

I've these languages: $$ \overline L = \left\{a^{n^2} \big| n\geq0 \right\} $$ $$ \overline L = \left\{a^n b^n c^n \big| n\geq0 \right\} $$ $$ \overline L = \left\{ww \big| w\in \{0,1\}^* \right\} ...
-5
votes
1answer
30 views

What is the language generated by the following grammar? [closed]

Could please tell me the language generated by this grammar? S->iS |iSeS|ε
-5
votes
1answer
28 views

Show that this grammar is ambiguous [closed]

$E\rightarrow E+E | E*E | \neg E | (E) | num$ prove the above grammar is ambiguous by giving 2 different parse trees for the expression 4*(~3+5)
3
votes
1answer
50 views

How do I reconstruct the forest of syntax trees from the Earley vector?

Using the Earley vector as a recognizer is quite straightforward: when the end of the string is reached, you just have to check for a completed axiomatic production started at position 0. If you have ...
3
votes
1answer
66 views

Recursive-descent parser for the grammar S -> S(S)S | ε

I'm studying (for self-betterment - I don't go to school) the 2nd edition of Compilers: Principles, Techniques and Tools by Aho et al. I'm not sure how to do Exercise 2.4.1 (b), which is to construct ...
1
vote
0answers
53 views

LL(1) grammar for postfix ternary operations

Suppose the task is to make an LL(1) grammar for postfix operations, where the only operation is ternary. Obvious approach is $N$ - number $O$ - operation $S$ - expression ...
-3
votes
2answers
78 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?
0
votes
1answer
35 views

CFL, pumping lemma

I have difficulty with proving that the language $ L = \{ a^p b^q | p \ge 1 , q \ge 1 , p \ge q^2 \vee q \ge p^2\}$ $ w = uvxyz $ I've chosen word $ w = a^{N^2} b^N $ where $ N $ is a constant ...
2
votes
1answer
76 views

Can every DCFG be converted to DGNF?

I know you can convert every context-free grammar into Greibach normal form grammar. But can I convert every deterministic context-free grammar into deterministic Greibach normal form grammar?
0
votes
0answers
35 views

Context-free Language, Pumping lemma

I want to prove that $ L = {a^n b^m c^{ \lfloor \frac{n}{m} \rfloor } } $ isn't context free language, so I choose N - constant from lemma so the word is $ w = a^N b^N c $ and $ w = uvxyz $ 1 ...
1
vote
1answer
90 views

Resolve left-rescursion

Can anybody give me a hint on how to get rid of the left recursion in the following grammar? $$A \rightarrow B \mid a$$ $$B \rightarrow b \mid C \mid D \mid E \mid F \mid G$$ $$C \rightarrow c \mid A ...
3
votes
0answers
41 views

Automatic tool for resolving left-recursion within CFG [closed]

Though facing the fear that someone might not like my question but does somebody know a useful tool to either resolve left recursion or to simplify a context-free grammar automatically ? I need ...
-1
votes
1answer
31 views

writing a Context free grammar for a language [closed]

Hi I have two question about this language: L = {a^i b^j c^k | i = 2*j OR j=2*k } 1)Finding a CFG 2)If in condition part we put AND instead of OR , is this language remains CONTEXT FREE or not ?? ...
0
votes
1answer
34 views

LR(0) parsing: how can I know sets of items corresponding to states?

I'm studying LR(0) parser. But I don't understand how sets of items corresponding to states can be calculated. I think The author would miss some information readers must know. Given the following ...
0
votes
1answer
59 views

Build a context-free grammar for a context-free language [duplicate]

A context-free language is defined by its description: $L=(a^{2k} \space b^n \space c^{2n} \mid k \geq 0, \space n > 0)$ For example: $bcc, aabcc, aabbcccc, bbcccc$ How to build a context-free ...
3
votes
1answer
28 views

Situations where Kleene star of A is context-free, but A is not

This question appeared on my Theory of Computer Science final: True | False: $A^*$ is context-free $\implies$ $A$ is context-free. My professor says the answer is false, and I believe him, but am ...
-1
votes
1answer
39 views

Eliminating Left Recursion [duplicate]

Hello I have the above Context Free Grammar and I try to eliminate the left recursion so I can pass it to a tool. Any techniques I've read so far doesn't help me so a little help would be appreciated. ...
0
votes
1answer
34 views

Is my grammar correct for this context-free language?

$\{a^nb^2a^n \mid n \ge0\}$ I'm studying for my final and I came across this language. I haven't dealt with characters of the same length on opposite ends with something in between. I came up with ...
-2
votes
1answer
58 views

Automata Theory Questions: Rule Trees, Context-Free Grammar, Proving Ambiguity [closed]

I'm currently taking a class in Automata Theory and it's kicking my butt. I have an assignment that my teacher gave me that consists of three questions. I have no idea where to start. My teacher and I ...
3
votes
1answer
42 views

Building Simple Parse Trees

I am trying to learn how to build parse trees. I have watched videos and tried to do some on my own, but am a little lost. In this example, I am given the following: $$ \begin{align*} &S\to(L) ...
3
votes
0answers
55 views

Prove or disprove that every $L$ in this class is a CFL iff $L$ is equivalent to a substitution

Let $L$ be a language with every string of the form $(w_i\#)^*$ with $w_i\in\{0,1\}^*$. Set $w'\sim w$ if there is a permutation $\pi_1$ such that $w_i=w'_{\pi_1(i)}$ for all $i$. If additionally ...
2
votes
1answer
56 views

Is there a Context-free grammar for this language?

Is there a Context-free grammar for the following language: $L=\{ x\#1^m|x \in \{0,1\}^* \space and \space the \space m^{th} \space char \space in \space x \space ...
1
vote
1answer
58 views

Prove not context free

How can we prove that: $$ L = \{ w_1\#w_2 \mid w_1 \in w_2;\; |w_2| > |w_1|;\; w_1 , w_2 \in \{0, 1\}^*\} $$ is not context-free? The language defines $w_1$ as a sub-string of $w_2$, and they ...
2
votes
1answer
61 views

Chomsky normal form: epsilon rule

I have pretty simple question, but still can't find an answer just googling it. I'm trying to understand Chomsky Normal Form (CNF). There are three production rules: $A \to BC$ $A \to \alpha$ $S ...
1
vote
1answer
50 views

How to check ambiguity of a specific grammar

Giving the following Grammar: S → ^ | SaSMSM | SMSaSM | SMSMSa M → b | c ^ means eopsilon. How can i check whether its ambgious or not? My intuition is ...
0
votes
2answers
73 views

Find a CFG for a language

In an assignment I've been asked to find a CFG for $a^x b^y a^z b^w$, where, $x,y,z,w \in \mathbb{N}^+$, $y > x$, $z > w$, and $x+z = y+w$. A hint was given, think of the language as $(a^p ...
-1
votes
1answer
46 views

Show L is not context free using the CFL pumping lemma

I am trying to use the pumping lemma to show this language is not context free: $L = a^nb^{n+1}c^{2n} : n \ge 0$ So I took $z = a^mb^{m+1}c^{2m}$ where $|z| = 4m+1 > m$. We can decompose $z = ...
3
votes
2answers
257 views

Proving that a word is *not* generated by a context-free grammar

I saw the answer in one of the solutions and I cannot figure out how they got the answer. The question is asked if the word is in the language or not for CNF... How did they get the answer so that ab ...
2
votes
1answer
48 views

How do you describe a language that is generated by Context Free Grammer [closed]

I am familiar with describing Regular Expressions but when it comes to describing CFG I get confused. Do you describe it in words like you would regular expressions or do you do something like this ? ...
2
votes
0answers
83 views

Good introductions to Formal Language Theory and Formal Grammars

Does anyone know any good introductions to Formal Language theory and Formal Grammar, that cover the mathematical basis of Syntax and things like context free grammars and pushdown automata. In ...
0
votes
1answer
45 views

a regular language so that $unary(L) \notin $Context Free Languages [closed]

I need a regular language $ L\subseteq \{0,1\}^{*} $ so that $unary(L)$ is not context free. unary of $L$ is defined by: $$unary(L) = \{0^{1x} : x \in L \}$$ Example $L = \{0, 11\} $ $\rightarrow ...
1
vote
3answers
238 views

How to find whether a grammar's language is finite or infinite?

I have this context-free grammar and I want to find out whether its language is finite or infinite. ...
1
vote
1answer
46 views

Why does left recursion have to be eliminated? [closed]

For example, Let the Grammar be: S->Sa|B Thus, S->Sa->Saa->...->Saa...aaa->Baa...aaa What's wrong with ...
1
vote
2answers
95 views

proving that if $\{w\$w^R | w \in L\}$ is context-free then $L$ is regular [closed]

I am trying to prove this following theorem, can someone help please? Let $L$ be a language over the alphabet $\Sigma = \{ a,b \}$. If $L' = \{ w\$w^R \mid w \in L\}$ is context-free, then $L$ is ...
1
vote
2answers
218 views

Find a context-free grammar for the language $L=\{a^nb^m\mid 2n<m<3n\}$ [closed]

I need to find a context-free grammar for the following language which uses the alphabet $\{a, b\}$ $$L=\{a^nb^m\mid 2n<m<3n\}$$
3
votes
1answer
80 views

Show that the pumping lemmas for context-free and regular languages are equivalent for unary languages

I want to show that for any language $L \subseteq \{ a \}^* $, $L$ satisfies the pumping lemma for context free languages if and only if it satisfies the pumping lemma for regular languages. I know ...
0
votes
2answers
78 views

How many states when converting CFG to PDA

When converting a CFG to a PDA I know that you get three main states, Qstart, Qloop and Qaccept. But Qloops will need a various amount of states, and my question is how many? Is there a way to find ...
2
votes
0answers
64 views

If $L_1$ is regular and $L_1 \cap L_2$ context-free, is $L_2$ always context-free? [closed]

If $L_1$ is a regular language and $L_1 \cap L_2$ is a context-free language, does it mean that $L_2$ is a context-free language too? I attempted to prove that $L_2$ was not required to be ...
3
votes
1answer
115 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 ...
0
votes
1answer
54 views

Can a context free grammar for $L$, generate a string not in $L$?

from Sipster's definition: Any language that can be generated by some context-free grammar (call it $G$) is called a context-free language (CFL). However, can $G$ generate strings that are not in the ...
1
vote
0answers
37 views

Prove a language is context-free [closed]

for this problem, it asks to prove that A and B are context free, however the CFL pumping lemma doesn't prove that. It proves when languages are not context free. Would the easiest way to prove ...
2
votes
1answer
50 views

Is $L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n $ for some natural number n $\}$ context free?

I was wondering if this language is context-free: $L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n $ for some natural number n $\}$ I know that this language is not regular because it fails the pumping lemma ...
1
vote
2answers
38 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: ...
0
votes
2answers
76 views

Proving that context-free languages are closed under inserting symbols [closed]

This is a theoretical computer science question, regarding the proof of whether or not context-free languages are closed under an operation. This means basically that any context-free language which ...
0
votes
1answer
29 views

Construct context free grammar from language

I have been starting to learn about CFGs and PDAs and have gotten familiar with the simple stuff. I have been able to construct CFGs for simple languages but this question is more specific: $\lbrace ...