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
1answer
30 views

Does removal of unit production from the grammar may increase number of total production?

I have doubt ! Problem is There are m variable in a grammar. The number of productions after removal of unit productions in the worst case is ,(Assume there are no null productions) (a) O(m) ...
0
votes
1answer
51 views

How to construct a grammar that generates language L?

I'm in a Formal languages class and have a grammar quiz coming up. I'm assuming something like this will appear. Consider the alphabet $\Sigma$ = {a, b, c}. Construct a grammar that generates the ...
1
vote
1answer
42 views

Whats Wrong with this LL(1) Grammar?

I am trying to build a LL(1) parse table for the following Grammar: S -> L L -> L : L L -> id R R -> ( L ) R -> ( ) R -> Epsilon There are two Problems here. First the L rules are a left recursion ...
3
votes
1answer
27 views

Equivalence of two context free grammars [for the given example]

I know that in general it is undecidable whether two context free grammars generate the same language, but I have to do this exercise and I am finding myself somewhat stuck: G1: S->e|aB|bA ...
3
votes
1answer
25 views

Arden's lemma applicability on context free grammars

The Arden's lemma states that there exists a solution to the equation between regular expressions r = sr + t, with r unknown, and it is s*t. I went through some other topics on the forum and I always ...
1
vote
0answers
16 views

How equality of item (production state) is defined in LR parser?

Whenever I read about equality I took it for granted, but few days ago I wondered if my understanding is not too shallow. Consider such example (taken from: ...
2
votes
1answer
38 views

Have non-regular language classes of infinite words been studied?

For regular languages we have $\omega$-regular languages which extend them to infinite words. Are there such extensions for CFG's, CSG's and recursively enumerable languages?
0
votes
1answer
24 views

Chomsky NF or Greibach NF benefits for LR parser?

Are there any benefits of having grammar in CNF/GNF for LR parser? I have those in mind: total speed of creating a parser (that is time for creating CNF/GNF out of the grammar, and then creating ...
0
votes
1answer
42 views

Decidable language: set of context-free langauges containing 1 string

ONE = {(G) : G is a CFG such that L(G) contains exactly one string} . I know to prove this is decidable I need to create a DTM that would recognize it and HALT on all input. I am struggling at ...
0
votes
1answer
28 views

Can I couple non-terminals in context-free grammars?

If I had productions like so... $S \rightarrow A1B$ $A \rightarrow \epsilon$ $A \rightarrow 0$ $B \rightarrow \epsilon$ $B \rightarrow 1$ If I only want strings $\{\epsilon1\epsilon, 011\}$, am ...
1
vote
2answers
52 views

How to read BNF syntax of C?

Today I heard of BNF which is a language for languages. Also heard that it specifies the entire syntax of C in four pages. So I thought of checking it out. After reading through this page, I got a ...
6
votes
1answer
52 views

Can an Earley Parser be made into a fuzzy parser similar to the Levenshtein Automata Algo for DFA?

There's a way to perform fuzzy parsing (accepts strings even with typos to a certain edit distance), with a DFA and a run-time constructed Levenshtein Automata of the input word. Can something ...
4
votes
2answers
79 views

From context-free to context-sensitive

I have a context-free language $L(G)$. I'm reading in a book that $L(G') = L(G) - \{{\epsilon}\}$ is context-sensitive but I cannot find a proof or confirmation of this fact; moreover, in other texts ...
0
votes
0answers
34 views

Can we remove unit productions First Before removing Null productions?

My professor have asked me strange question , about converting from Context free grammar to chomsky normal form , Can we remove unit productions first from CFG if possible , before removing null ...
6
votes
4answers
61 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 ...
2
votes
1answer
32 views

Inducing a context free grammar [closed]

I have a file containing a subset of possible strings from a context free language. I am looking for a mechanism to induce the grammar from this information. Is that possible?
0
votes
1answer
59 views

Regular Expression from Context Free Grammar [duplicate]

The purpose of this exercise is to write a program that recognize all the words derived from this grammar. The time complexity of this program must be O(n) hence i must be able to derive a regular ...
2
votes
1answer
64 views

fixed point in regular expressions

I've posted this question first on StackOverflow but this section seems more suited for this kind of questions. Also I'm not trying to simply solve this exercise (it is a "parsing" exercise, once I'll ...
0
votes
1answer
30 views

prove language is Context-free and not regular [duplicate]

I have to prove that $\left \{ a, b \right \}^{\ast} - \left \{ a^ib^i | i\geq 0 \right \}$ is a context-free language and it's not regular. So far I've got that this language is not regular because ...
3
votes
1answer
41 views

Proving that if $L=\{ a^n b^n c^n \colon n\ge 0 \}$ than $L\notin CFL$ [closed]

I'm going over "Introduction to the Theory of Computation" by Michael Sipser in which there's an example of using the pumping lemma for CFLs to prove that $L=\{ a^n b^n c^n \colon n\ge 0 \}$ is not a ...
0
votes
0answers
22 views

CFG. Ensure that $n\neq m$ twice in $L=\{a^m b^n c^m d^n, m\neq n\}$ [duplicate]

During the formal language exam, the professor allowed to find a CFG to following language: $\{a^m b^n c^p d^q, m\neq n\wedge p\neq q\}(1)$, because neither he saw a solution (He passed a test without ...
7
votes
1answer
91 views

How much bigger can an LR(1) automaton for a language be than the corresponding LR(0) automaton?

In an LR(0) parser, each state consists of a collection of LR(0) items, which are productions annotated with a position. In an LR(1) parser, each state consists of a collection of LR(1) items, which ...
0
votes
2answers
32 views

Push down automata what to do when there is no suitable transition

This is a question that has emerged from a recent quiz I have taken. In short Consider the following transitions on a push down automaton. Assume the starting state is q. Which one of the ...
-2
votes
1answer
53 views

How to convert this type of languages to Context Free grammar?

As I've already asked my Question about the solving Context Free Grammar $L = \{a^n b^m c^p \mid n = m + p + 2\}$ Can this language be defined by a Context Free Grammar? Now i have just changed ...
-1
votes
1answer
144 views

Does every language that fulfills the regular Pumping conditions also fulfill the context-free ones?

Let L be a language that fulfills the properties implies by the Pumping lemma for regular languages. Does L necessarily fulfill the corresponding properties of the Pumping lemma for context-free ...
0
votes
0answers
10 views

Construction of NPDA with inequality check [duplicate]

I'm currently struggling to construct a nondeterministic PDA with an amount of states in $O(n)$ that accepts the following language: $L = \{wcx \, | \, w,x \in \{a,b\}^n \land w \not= x\}$ with c ...
2
votes
2answers
143 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 + ...
0
votes
1answer
33 views

Proving that a set of grammars for a given finite language is decidable [duplicate]

Let the language $$L = \left\{ \langle G \rangle \ |\ L(G) = \{1,\ldots , 1000\}, \text{ G is a CFG }\right\}$$ Prove that $L \in R$. Well, I think that for a start we need to check whether or ...
1
vote
0answers
61 views

Are DCFLs closed under concatenation with a regular language?

I have found various opinions saying they are (a link to one is given in D.W.'s comment). However, a proof that DCFLs themselves are not closed under concatenation found here on StackExchange seems to ...
3
votes
1answer
27 views

Proof that CFL aren't closed under intersection using synchronous parallel (N)PDA composition

It is well known that the class of CFLs is not closed under intersection as follows e.g. from the following example: $$L_1 \cap L_2 = \left\{ a^mb^mc^n \mid m,n \ge 1 \right\} \cap \left\{ a^mb^nc^n ...
-1
votes
1answer
38 views

Chomsky Normal Form-remove unit production

In the step of removing unit productions when converting a grammar to Chomsky normal form, I sometimes found that the variables may end up having the same production bodies. Is this possible? If so, ...
0
votes
0answers
58 views

The pumping lemma - Proving that this language is NOT context free

I would like to find out if this language is context free or not: $\qquad L=\{a^{i}b^{j}c^{k} \mid i<j,i+2j+3<k\}$. I've tried to apply the pumping lemma taking out $w=a^n b^{n+1}c^{3n+6}$ ...
0
votes
1answer
50 views

Context free grammar for this language [duplicate]

Is this language Context Free? $L=\{a^{n+3} b^{2m} \mid n \neq m \}$ I think that I could split the languages into $L_1$ and $L_2$ with the conditions $n<m$ and $n>m$, provide 2 CF grammars ...
0
votes
1answer
67 views

Using the pumping lemma to prove that a language is context-free [duplicate]

I am new to automata theory. Could you give me a little hand with the correct use of the pumping lemma? I understand now how to proof a language is not context-free, but how do I use the pumping ...
0
votes
0answers
20 views

Prove this language is not CFL [duplicate]

I have this language: $L = \{a^{n+2} b^m a^{2n} b^{3n}\mid n,m >=0 \}$ and I am trying to prove that it is not CFL. I assumed that my word is $a^{p+2} b^m a^{2p} b^{3p}$ (where $p$ is the pumpung ...
0
votes
1answer
38 views

How can I prove this language is not CFL? [duplicate]

I have a question to find out that $L = \{a^m b^n\mid n>0, m - is prime \}$ is CFL or not. I know that it is not a CFL. But I don't know how to prove that. I know how to prove that $L = \{a^m\mid m ...
-1
votes
1answer
28 views

What would be CFG for all strings which does not contain bbb?

Is there a way to get complement? Following is my solution for CFG of all strings that DON'T contain bbb. ...
-2
votes
1answer
31 views

CFG for all string that don't end at ba?

Here is my solution: S-> Sab|Sbb|Saa S->aS S->bS S->ε Is this solution right?
0
votes
1answer
46 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
79 views

Is the language $L=\{a^{2^{n}} \mid$ n is a natural number$\} $ context free?

I have to determine, and prove, whether the language $L=\{a^{2^{n}} \mid$ n is a natural number$\}$ is context free or not (if it is by a grammar and not by the pumping lemma). I tried to construct ...
6
votes
1answer
52 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 ...
9
votes
0answers
68 views

Machines for context-free languages which gain no extra power from nondeterminism

When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines. For the ...
3
votes
1answer
70 views

Removing left-recursion in grammar while maintaining left-association of operator

I have a problem with this exercise: Let G be the following ambiguous grammar for the λ-calculus: E → v | λv.E | EE | (E) where E is the single ...
1
vote
2answers
101 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 ...
21
votes
2answers
2k views

What does “context” in “context-free grammar” refer to?

There are lots of definitions online about what a Context-Free Grammar is, but nothing I find is satisfying my primary trouble: What context is it free of? To investigate, I Googled "context ...
0
votes
0answers
36 views

Context-free with single terminal symbol — regular language [duplicate]

I have the following problem to solve: Show that if G is a context-free grammar and Σ consists of just one terminal symbol, then L(G) is regular. It is problem 4.26 from the book "Formal models of ...
-2
votes
1answer
57 views

Is the language given by this CFG regular? [duplicate]

S → AB | C A → aAb | ab B → cBd | cd C → aCd | aDd D → bDc | bc How can I prove that this language is regular or not? I need your help. It also has two ...
1
vote
1answer
27 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, ...
6
votes
1answer
81 views

TM recognizing $0^n1^n$ requires Ω(log n) space

I am trying to prove that any deterministic 1-tape Turing Machine which recognizes the language $L = \lbrace{0^n1^n | n \geq 0 \rbrace}$ requires $\Omega(\text{log }n)$ space. I believe this can be ...
-3
votes
1answer
28 views

Chomsky Normal Form of |a|<|b| [closed]

Hello Everyone I was hoping I could ask you to check to my work on this CNF, These are a pain to me and I want to make sure I'm doing it right the first time ...