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
votes
0answers
10 views

Construction of a nondeterministic pushdown automation

I have a solution for the pushdown automaton that accepts the language $$\{x\#y \mid x,y\in \{0,1\}^* \text{ and } x\neq y\}\,,$$ which looks like this: I am trying to work from this in order to ...
3
votes
2answers
180 views

complexity of determining whether a language given by context free grammar is empty

I know that it is decidable problem to check whether given context free grammar represents empty language -- for instance, AFAIR one could convert it to Chomsky normal form, and then check if any word ...
0
votes
1answer
56 views

Intersections of some context-free languages

Suppose We have Some language as follows: $L_1=\{w^* | w=x \text{ and } x \in \Sigma^*\}$ $L_2=\{ww^R ww^R | w \in ( \Sigma + \Sigma)^*\}$ $L_3=\{w | w=xy, x,y \in \Sigma^*, y \text{ is a ...
2
votes
2answers
71 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 ...
2
votes
1answer
113 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 ...
0
votes
2answers
67 views

Finding context free grammar for this language?

I needed help finding the context free grammar of this string $$ 10^{n}10^{n}1 $$ So far an idea I have is $$ S\rightarrow 1S1S1\mid 0S \mid \varepsilon $$ Any assistance you can provide would be ...
0
votes
0answers
35 views

How to prove a CFG is equivalent to a language [duplicate]

I have to prove the following statement: Prove that $\{0^m1^n | 0 ≤ m < n\}$ is the language generated by $S \rightarrow 0S1| A$ $A \rightarrow 1A | 1$ I can clearly see that the ...
3
votes
0answers
13 views

Using the Chomsky-Schutzenberger theorem to prove a language is not context-free?

The Chomsky-Schutzenberger theorem states that a language $L$ is context-free iff there is a homomorphism $h$, a regular language $R$, and a paired alphabet $\Sigma = T \cup \overline{T}$ such that $L ...
9
votes
1answer
247 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 ...
1
vote
1answer
94 views

Unambiguous CFG for $a^ib^j$ where $i \le j \le 2i$

could you please help me for finding an unambiguous CFG for the following expression: $a^ib^j$ where $i \le j \le 2i$
1
vote
1answer
42 views

Context Free or Context Sensitive and why

I was given two languages $$L_1=\{0^k1^k0^m\mid k,m \in \mathbb{N}\text{ and }k < m\}$$ and $$L_2=\{a^mb^{m+1}\}$$ and I was asked to prove whether they are context free or sensitive. For ...
1
vote
1answer
50 views

Are context free grammars the only ones that have parsing trees?

As I understand, the generation process of a string in a context free language according to its context free grammar can be represented as a tree. For a formal language which can have a formal ...
0
votes
1answer
27 views

Grammars: is there some connection between non-terminals $S$ and $S'$?

Given a grammar such as the following, does $S'$ have some special meaning or does it just denote another non-terminal like $B$, $A$, $P$, $Q$ etc.? $$\begin{align*} S &\to aBS'\\ B ...
-2
votes
1answer
104 views

Why is the language of even-length non-palindromes context-free?

We know $L_1=\{w_1 w_2 \in (a+b)^*\mid |w_1|=|w_2|, w_2 \neq w_1^{\;\mathrm{R}}\}$ is a context-free language. Can anyone help me produce a PDA or give me any hint how I can quickly understand why ...
1
vote
3answers
99 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
38 views

Find an unambiguous grammar [closed]

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
51 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
74 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
155 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 ...
-5
votes
1answer
35 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
31 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)
5
votes
1answer
69 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
0answers
77 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
65 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
80 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
43 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
39 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
106 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
54 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
43 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
45 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
63 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
29 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
48 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
37 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
88 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
52 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
56 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
67 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
60 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
73 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
56 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
83 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
50 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
280 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
51 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
104 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
50 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
279 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. ...