Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
6
votes
1answer
319 views

Why is ww a linear indexed language while www is not?

I am a little bit confused on one idea regarding indexed languages. $\{ww \mid w \in \{a,b,c\}^* \}$ is a linear indexed language, but $\{www \mid w \in \{a,b,c\}^* \}$ is not a linear ...
5
votes
2answers
934 views

How to get 2-state PDA for CFG?

I'm studying for my Computing languages test and there's one idea I'm having problems wrapping my head around, as far as I know for any Context Free Grammar (CFG), we can design a 2-state Pushdown ...
0
votes
1answer
357 views

Eliminating $\varepsilon$-productions during elimination of left recursion

I'm following the algorithm for left recursion elimination from a grammar. It says remove the epsilon production if there is any. I have the grammar $\qquad S \to Aa \mid b$ $\qquad A \to Ac \mid Sd ...
0
votes
1answer
240 views

Is this language context free?

In a recent test, I was asked to recognize if the below language is context free: $\qquad\displaystyle L = \{0^{n+m}1^{n+m}0^m \mid n,m \geq 0\}$ I think it is context free, and can be accepted by ...
2
votes
2answers
1k views

Need solution for infinite right recursive grammar in Predictive parsing?

i am new to compiler design, currently studying Ullmans book on this.He says: Problem with predictive parsing (both recursive and non recursive) is that Left recursive productions can go infinite ...
1
vote
3answers
874 views

Why isn't every monotonic grammar context sensitive free?

The question is really confusing me. I know every context sensitive grammar is monotonic but not vice versa. e.g. AB--->BA is monotonic but not context sensitive. Can someone explain to me in simple ...
1
vote
0answers
52 views

Is this theorem about left-factored grammars correct?

I am working on CFG grammars, LL grammars in particular and I encountered the following theorem in the slides of presentations written by my professor: A CFG grammar cannot be left-factored if all ...
7
votes
1answer
787 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 ...
17
votes
2answers
17k views

Is the complement of { ww | … } context-free?

Define the language $L$ as $L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$. In other words, $L$ contains the words that cannot be expressed as some word repeated twice. Is $L$ context-free or not? I'...
2
votes
1answer
76 views

“Grammar inference” for 2-D images

Others have studied the following question: given a set of words $w_1,w_2,\dots \in \Sigma^*$, find a regular grammar (or a context-free grammar) that generates all of those words, is "natural" in ...
17
votes
1answer
23k views

Intersection of context free with regular languages

The intersection of a context free language L with a regular language M, is said to be always context free. I understood the cross product construction proof, but I still don't get why it is context ...
26
votes
2answers
28k views

How to prove that a language is context-free?

There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free? What techniques are there to prove this? Obviously, one way is to exhibit ...
2
votes
2answers
167 views

Is the language with decreasing numbers of a, b and c context-free by pumping lemma?

So I've been given the following language on an assignment. It is the only question I have left of 10, and I've been racking my brains out trying to solve it for hours. $$L=\{w:w\in(a+b+c)^*, n_a(...
-1
votes
1answer
97 views

L is a regular language and w is any word, not necessarily in L. Show that L is regular

$L$ is a regular language and $w$ is any word, not necessarily in $L$. We define the set as $$L/w = \{x \in \Sigma ^* \mid xw \in L\}.$$ Show that $L/w$ is regular. I'm really struggling with this ...
1
vote
1answer
685 views

Converting to Chomsky normal form

Im having some problems with a qeuestion regarding converting a context free grammar to chomsky normal form. I have S -> abC | babS | de C -> aCa |b I know what to do with the case ...
1
vote
2answers
3k views

CFG for $\{a^ib^jc^k \mid i \neq j+k\}$

I am trying to design a context-free grammar for the language $L = \{a^ib^jc^k \mid i\neq j+k\}$ over the alphabet $\Sigma = \{a,b,c\}$. I know that I can split this up into the union of two cfg's $...
1
vote
1answer
1k views

Rules regarding Chomsky Normal Form (CNF) grammars

I'm writing a context-free grammar that I hope will be in Chomsky Normal Form, and I have two questions: Can I use a single variable (a non-terminal) on the left-hand side of multiple rules? Can I ...
2
votes
1answer
301 views

Automatic speech correction

When we are trying to learn a new language without any help from native speakers, the first thing we need is something/someone to correct our grammatical mistakes/improper word selection. So is there ...
0
votes
1answer
324 views

conversion of this grammar to CNF

My task is to convert the following grammar to CNF: $S \to SS \mid (S) \mid \lambda$ after removing lambda productions: $S\to SS, S\to (S), S\to(), S\to S$ after removing unit productions: $S\to ...
0
votes
1answer
2k views

Is my proof for a context free language correct? Same number of a's as b's

I have the following grammar G: $$ \begin{align*} &S \to aB|bA \\ &A \to a|aS|bAA \\ &B \to b|bS|aBB \end{align*} $$ I am going to prove that this language L(G) consists of words with the ...
4
votes
3answers
252 views

Designing a CFG that produces as many c's as the difference of numbers of a's and b's

The question is to design a CFG for the language of words that have as many c's as the difference of numbers of a's and b's, that is $\qquad\displaystyle L = \{(a^l)(b^m)(c^n) \mid l, m \in \mathbb{N}...
3
votes
1answer
65 views

Generalized operators for programming languages

After asking this question on stackoverflow, it has changed slightly. Is there a way to represent a grammar as a basis for a vector space and represent a program as an object that lives in that ...
1
vote
2answers
92 views

Grammar generating specific language

Construct a context-sensitive grammar that generates L: L = {a^n b^m c^k|k>n, k>m} I believe my productions should go along this lines: ...
2
votes
2answers
414 views

Recognizing finite state machines with repetition

I'm interested in finite state automata which have the capacity to require repetition. That is, the machine may be in a state in which the next character may be any character from set $S$, but, ...
4
votes
1answer
3k views

What is the advantage of Greibach Normal Form over Chomsky Normal Form?

I wanted to know the pros and cons of Chomsky normal form and Greibach normal form.
2
votes
2answers
3k views

Context Free Grammar for $\{0^n1^n \mid n \geq 0\}^*$

Give a context free grammar for the following language over $\Sigma = \{0,1\}$: $ L = L_1^* $ where $ L_1 = \{0^n1^n : n \geq 0\}$. Not really sure where to start with this one. Any help is ...
1
vote
1answer
1k views

Derive a Context Free Grammar from a language

I am having challenges (in two phases) with creating a CFG. Derive the CFG for the following language Show parse trees for the strings cacab and aacabbb obtained from the grammar designed above. I ...
0
votes
1answer
322 views

Reducing states of a GTG

I used this generalized transition graph with 3 states and got an equivalent generalized transition graph with 2 states: GTG: Equivalent with 2 states: I'm not sure about the regular expressions ...
2
votes
1answer
114 views

Regular Expression as basis for creating this grammar

I made a right-linear grammar from a regular expression: The alphabet is: $Σ = \{a, b, c\} $ Regular expression: $r = cc^{*}(ba)^{*}bb$ My solution, it seems a little too short like I'm leaving ...
0
votes
0answers
122 views

Making a regular grammar for this language

I'm trying to make a regular grammar for this language: Where the alphabet is $ \Sigma $ = $\{a,b,c\}$ It seemed like it would go well with a right-linear grammar. This may be disastrously wrong, ...
13
votes
5answers
5k views

How is non-ambuiguity different from determinism?

I am trying to understand what is meant by "deterministic" in expressions such as "deterministic context-free grammar". (There are more deterministic "things" in this field). I would appreciate an ...
0
votes
2answers
191 views

Equivalence of Context-Free-Grammar and Context-Free-Grammar in CNF

Given any Context-Free-Grammar, $G$, and another in Chomsky Normal Form, $G_c$, how can we check if both $G$ and $G_c$ generate the same language? One of the trivial ways I know of is to convert $G$ ...
3
votes
1answer
1k views

Is this an example of a type-0 grammar that is not context-sensitive?

A type-0 grammar generates a recursively enumerable (RE) language. A RE language is also known as a semi-decidable language. A semi-decidable language is a particular kind of undecidable language: ...
3
votes
2answers
142 views

Can a method be written if the language is undecidable?

If a language is decidable, we can write a method that always halts and returns true for each string that is an element of the language and ...
2
votes
2answers
107 views

Class of a Language [duplicate]

What are the common ways to check if a given language is regular, context free, or context sensitive? Any surveys or notes would also be helpful. There's no need to describe your suggestions. eg. it ...
2
votes
2answers
308 views

Does this language have a context-free grammar?

Here is a question that I encountered in one of my exams: Find one context-free grammar that recognizes the language: $\qquad L = \{a^n(b^mc^m)^pd^n \mid m, n, p \geq 0\} $ Can you find such a ...
3
votes
3answers
366 views

Formal language without grammar

Definitions: Alphabet $Σ$: finite, non-empty set Language: subset of $Σ^*$ Grammar: Unrestricted grammar (Chomsky Type 0) Language of a grammar: all words that can be produced by applying $P$ ...
1
vote
2answers
102 views

Trying to understand a token file for lexical analysis

I am reading this article about compiler. I am facing some problem in understanding the content of the token file. Specifically, what is the meaning of the following lines: ...
1
vote
2answers
108 views

Grammar to Language

Having: $\qquad \begin{align} S &\to aT \\ T &\to a \mid UTV \\ U &\to ab \mid ba \\ V &\to ac \mid ca \end{align}$ What language would be generated by this? How ...
2
votes
0answers
185 views

Constructing a Context Free Grammar for checking non-equality of strings [duplicate]

I have been studying the book Introduction to Computation by Michael Sipser on my own, and I'm stuck on this exercise from the chapter on Pushdown Automato and Context-Free Languages. The exercise is ...
-1
votes
1answer
121 views

Representing grammar for list/dictionary with optional end separator as LL(1)

Considering a grammar that includes a dictionary or list with an optional terminal separator - e.g.: $$ \begin{align} obj \to & dict \\ &\mid OTHER \\ dict \to & \...
0
votes
1answer
385 views

Determine if two grammars for the same language are ambiguous

I'm reading the book: Formal Syntax and Semantics of Programming Languages. I don't understand this exercise: Consider the following two grammars, each of which generates strings of correctly ...
2
votes
1answer
980 views

If a parser can parse a non-deterministic grammar, is the parser non-deterministic?

I've written a recursive-descent parser generator, and I'm trying to classify it (call me a cowboy coder if you must). According to wikipedia, S → 0S0 | 1S1 | ε, ...
9
votes
3answers
629 views

Context-sensitive grammar for the language of words concatenated with themselves

I'm looking for a context-sensitive grammar that describes the following language: $L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\}$ . I've got problems with the fact that no rules such as $X \to \...
1
vote
3answers
172 views

How can I produce a summation function from this set of production rules for a grammar?

I am not entirely sure if the title is the correct way to phrase what is occurring. There is a recurring process which I decided to attempt to model using production rules similar to those used in a ...
2
votes
1answer
4k views

Does the empty language have a CFG in CNF?

I just not sure does empty set have a context-free grammar in Chomsky normal form? That is, for $B=\emptyset$, then a context-free grammar is $S \to S$, I think which doesn't have a Chomsky normal ...
2
votes
2answers
109 views

I'm lookin for a method to construct a particular grammar?

I'm looking for an algorithm to construct a grammar which, given a set of words which can have multiple identical symbols, represents a compressed version of this set, that is, I can generate only the ...
4
votes
1answer
2k views

Is this formal grammar context-free (CFG) but not context-sensitive (CSG)?

I have the following formal grammar: $$G= (\{S,A,B\},\{a,b\},R,S)$$ $$R=\{S \rightarrow A\ |B, A \rightarrow \varepsilon\ | aA\ |bA, B \rightarrow \varepsilon\ |Bb\ | b\}$$ Now, we see, the ...
2
votes
2answers
207 views

Proving that CFLs are closed under even-ness using grammars

This is a question from a 2007 exam paper for a course I'm studying, question 2 on page 2. Theorem: Let $L$ be a context-free language. Let $L_{even}$ be the subset of $L$ consisting of all the ...
2
votes
1answer
829 views

How to prove formally that grammar isn't LR(1)

I want to prove that grammar $$ \begin{cases} S'\rightarrow S\\ S\rightarrow aSb ~|~ A\\ A\rightarrow bA~|~b \end{cases} $$ isn't $LR(1)$. I've constructed parser table and got Shift-Reduce conflict. ...