We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
4
votes
2answers
227 views

Context free grammar construction

My problem with CFG is, I am to generally create ones that don't have requirements such as: $\qquad \{a^m b^n \mid m \le n \le 2m \}$ I have no clue where to begin, and how to approach it. I was ...
3
votes
2answers
1k views

Does a context-free grammar with multiple variables have a “starting” point?

So lets consider the following grammar $$ \begin{align*} S &\to 0 \mid 0A \\ A &\to 1 \end{align*} $$ would the string "1" be accepted by the language or must the language start with $S$?
3
votes
2answers
2k 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 ...
3
votes
3answers
4k views

How to convert a context free grammar (could generate regular language) to a right-linear grammar

Consider the context free grammar: $$S \rightarrow aSb \mid aSa \mid bSa \mid bSb \mid \varepsilon$$ It could generate regular language, which means it can be converted to a right linear grammar. Is ...
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 ...
3
votes
1answer
3k views

Grammar of regular languages vs. context free languages

Let $L$ be some language. What could you say about $L$'s grammar if it is a regular language, that couldn't be said if it was a context free language? For example, in case $L$ is regular, could you ...
3
votes
3answers
2k views

How to represent whitespace in a context-free grammar?

Say we want to support: xx The following grammar does accept it: S -> xAx A -> ε. because S => xAx => xx. But what about supporting: x x I realize this might be a stupid question but I'm really ...
3
votes
3answers
337 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$ ...
3
votes
3answers
464 views

Context-free grammar of the concatenation of a string S and subsequence of reversed S

I have to find a Context-Free grammar that generates the language: $L_1 = \{x\#y\ |\ y$ is a subsequence of $x^R$, and $x\in\{a,b\}^*\}$, $\Sigma=\{a,b,\#\}$ The concatenation of two mutually ...
3
votes
5answers
7k views

What is rightmost sentential forms?

I'm solving some past job interview problems. I met an embarrassing question about compilers. The question is : Consider the following grammar, with start symbol $E$: \begin{align*} E &\...
3
votes
2answers
217 views

Correspondence between automata and formal grammars?

From Wikipedia Since there is a one-to-one correspondence between linear-bounded automata and such grammars, no more tape than that occupied by the original string is necessary for the string ...
3
votes
2answers
3k views

Finding the grammar type of the programming language

How can someone find what type of grammar for a given programming language? Formerly I'm looking for a grammar type for most popular programming languages: C, C++, C#, Java, List, OCaml, Haskell etc.
3
votes
2answers
807 views

non LL(1) grammar but LL(1) language

I'm reading a Basics of Compiler Design and on page 84 it is making the following statement: A language may well be LL(1) even though the grammar used to describe it is not. Can someone give ...
3
votes
2answers
239 views

Figuring out the language of a non-linear CFG

I have the CFG G with the following production rules: $$ S \to aSaS \mid b $$ Is it possible to find $L(G)$? I have no idea how describe it by any pattern. I use grammophone to check example words, ...
3
votes
1answer
1k views

Grammar for a language: odd length, middle character not repeated

Consider the following language over the alphabet $\mathcal{A} = \{a,b,c\}$: $$L = \left\{w \in \mathcal{A}^* \mid \text{\(|w|\) is odd and the middle character in \(w\) occurs nowhere else in \(w\)} \...
3
votes
2answers
691 views

Pascal FOR loop with context free gramar

In Pascal For-do loops, there is a rule stating that one cannot modify the counter variable inside the body of the loop. To exemplify the rule, take the following Pascal ...
3
votes
1answer
834 views

How can I check that the language of one context-free grammar is a subset of a second context-free grammar?

Could you explain me, how can I check, that the language of first context-free grammar (G1) is a subset of the language of second context-free grammar (G2). G1 and G2 are two LL(1) grammars with ...
3
votes
2answers
3k views

Context Free Grammar for $a^*b^*c^* - \{a^n b^n c^n \mid n \geq 0 \}$ [duplicate]

I'm having trouble constructing a Context Free Grammar for the following language: $$a^{\ast}b^{\ast}c^{\ast} - \{a^{n} b^{n} c^{n} \mid n \geq 0 \}$$ I believe it's telling me that no string can be ...
3
votes
1answer
942 views

How to call something that can be either a terminal or a nonterminal?

I had written a compiler compiler a few years ago and I'm now cleaning it up, improving it, and turning it into C. I came across a terminology problem however that I remember in the past I couldn't ...
3
votes
2answers
163 views

How to prove the equivalence of two CFG for balanced parentheses?

Given two CFGs for balanced parentheses. $S \rightarrow SS \mid (S) \mid \epsilon$ $S \rightarrow S(S)S \mid \epsilon$ How do I show that they are equivalent? I have been able to show $ L(2) \...
3
votes
1answer
246 views

Semantic readings of the Lambek sequent calculus

I am reading Categorial Grammar: Logical Syntax, Semantics, and Processing by Glyn Morrill and I am stuck with the Fig. 3.9: Can someone explain this set of formulas and |.| function specifically? ...
3
votes
2answers
4k views

Defining a context-free grammar for $\{w \in \{0, 1\}^* : \#_0(w) = \#_1(w)\}$ [duplicate]

I have a language where each string in the language has even amount of $0$'s as $1$'s (e.g., $0101$, $1010$, $1100$, $0011$, $10$ are all in the language). I was hoping to define a context-free ...
3
votes
1answer
168 views

LL grammars and left-recursiviity

Why LL(k) and LL(∞) are incompatible with left-recursion? I understand that a LL(k) language can support left-recursivity provided that with k-overahead tokens can be resolved any ambiguity. But, with ...
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 \...
3
votes
1answer
61 views

Why are four context sensitive grammar (CSG) rules needed to represent AB -> CD?

In Wikipedia of Kuroda normal form, it says A straightforward technique attributed to György Révész transforms a grammar in Kuroda's form to Chomsky's CSG: AB → CD is replaced by four context-...
3
votes
2answers
1k views

CFG for language of all palindromes whose number of 1s is divisible by 3

The question is the following: Construct a CFG for $L_2 = \{w \in \{0, 1\}^* \mid w = w^R\text{ and the number of 1’s in $w$ is divisible by 3}\}$. I can construct a CFG for $\{w \in \{0,1\}^* \...
3
votes
1answer
157 views

Find a regular grammar that generates words with even number of a's

I have a language $L$ = {$vabu$ | $v$,$u\in \{a,b\}^*$, $|vu|_a = 0$ $($mod $2)$$\}$ where $|vu|_a$ is number of $a$ in $vu$. I came up with these rules: $\sigma \rightarrow aa\sigma | ab\xi$ $\...
3
votes
2answers
661 views

Examples for CFG that cannot be expressed by regular language

There are nice examples for context free grammars which cannot be expressed with regular language, for example the palindrome and a similar contrived example here, but they are very intuitively ...
3
votes
2answers
949 views

Converting REGEX to BNF grammar

Say I have a bunch of regex expressions which are used as filtering rules. (Any special extraction capabilities are unnecessary here, the set of regular expressions I have is only used for filtering ...
3
votes
1answer
66 views

Understanding this answer: A CFG defines a language as a the smallest solution to a system of language equations

Statement comes from this answer. A blanket statement that this is a well-known fact is made in this other question. I have never heard of a language equation. But I am just a student. Given the ...
3
votes
1answer
104 views

Prove that if you can derive w from α in n steps, it's possible with n left-derivations as well

My university's automata theory book claims that the following claim can be proved by induction but it doesn't bother showing the proof. I've tried to prove it myself but I got stuck at the ...
3
votes
1answer
1k views

An example of a non-regular grammar for a regular language?

I understand that a regular language can be specified by either regular or non-regular grammars. What is an example of a non-regular grammar for a regular language?
3
votes
1answer
62 views

Is $\{ w_1cw_2 \mid w_1 ≠ w_2 \}$ a context-free language?

Is the language $L_1 = \{w_1cw_2 ~|~ w_1,w_2 \in \{a,b\}^{\ast} \text{ and } w_1 \neq w_2\}$ a context-free language? It certainly isn't regular, but is it context free? I'm having trouble creating ...
3
votes
1answer
52 views

Create a grammar that generate the language a^n . b^m . c^q . d^p such that n + p = q + m

I'm stuck on this question. I'm struggling on how to keep track of the number of a and d I have generated. The professor hasn't given the correction. I have seen similar questions but the condition ...
3
votes
1answer
52 views

How to explain/understand brackets of applicative functor [[f u1… un]]?

I am reading article about Applicative Abstract Categorial Grammars http://okmij.org/ftp/gengo/applicative-symantics/AACG.pdf and this article uses brackets [[...]] for action on terms inside ...
3
votes
1answer
67 views

How do you call alternatives in the grammatical productions?

I have encountered a question, which asks what is a syntactic form. This motivated me to ask myself, what is the anatomy of the grammatic rule, ...
3
votes
1answer
145 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?
3
votes
1answer
123 views

parsing at semantic level due to ambiguities

I have a VHDL elaboration engine/simulator. As I understand it, the language syntax allows for ambiguities at syntax level. That is, an assignment ...
3
votes
1answer
2k 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 \to ...
3
votes
2answers
135 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 ...
3
votes
2answers
11k views

Grammar for describing boolean expressions with AND, OR and NOT

I wrote the following LL(1) grammar to describe the set of boolean expressions involving AND ,OR an ...
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
1answer
236 views

This doesn't seem like a valid regular grammar; my instructor says it is

The following is a screenshot of a lecture slide from my programming language concepts course: According to Wikipedia and other sources, a regular grammar is one that is either left linear or right ...
3
votes
2answers
485 views

How to check for ambiguous grammar if you don't know the string

Let's say I have a CFG grammar $G$ which describes some rules for language generation. How can you tell that grammar can generate ambiguous results for a string if you don't know that string? I know ...
3
votes
1answer
90 views

When did “regular” start referring to Type 3 languages/grammars?

In his 1959 paper, On Certain Formal Properties of Grammars, Chomsky defined a "regular" grammar as a specific form of a type 2 (context-free) grammar. (See Definition 8 of that paper.) He then goes ...
3
votes
2answers
177 views

Why do BNF specifications of C-like languages define expressions in terms of seemingly unrelated parent expressions?

Backus-Naur Form specifications for the grammars of languages like like C or C++ build up expressions with counter-intuitive definitions. For instance, a multiplication expression like ...
3
votes
2answers
383 views

Meta-grammar for context-free grammars

Formal grammars like regular expressions (REs) or context-free grammars (CFGs) specify languages, i.e. sets of strings over an alphabet. Grammars themselves can be seen as languages, e.g. the set of ...
3
votes
1answer
586 views

Why do we not use CFGs to describe the structure of lexical tokens?

This was an exam question for my course and I am struggling to actually answer it in a way that is not fluff. Here is my current answer: CFGs describe how non-terminal symbols are converted into ...
3
votes
1answer
2k views

Nullable nonterminals and recursion

I have two questions regarding nullable nonterminals in a grammar. Often a simple algorithm is described to find nullable nonterminals: Basis: if $A \rightarrow \epsilon$ is a production, $A$ is ...
3
votes
1answer
248 views

How to convert a grammar with finitely many ambiguous strings into a new, unambiguous grammar?

Suppose $L$ is an infinite CFL, and $G$ is a grammar with finitely many ambiguous strings which generates $L$. Is it possible to convert $G$ into an unambiguous grammar which also generates $L$? If ...