Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
1 vote
1 answer
20 views

What is a contracting grammar (in opposition to a non-contracting grammar)?

In the Chomsky hierarchy what is corresponding to a contracting grammar? I can find references to non-contracting grammars (which can be transformed into context-sensitive grammars accordingly to what ...
  • 221
1 vote
1 answer
27 views

How would this grammar be converted to a non-left recursive rule?

With recursive-descent parsing, direct/indirect left recursive rules do not allow top-down parsing. How would this grammar be converted to be non-left recursive? ...
  • 11
1 vote
1 answer
78 views

CFG for the language {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}

The question is the following: Construct CFG for the L = {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}. I am able to construct CFG for the set of all palindromes as below: S --> aSa | ...
0 votes
0 answers
17 views

First Set for this grammar? Is it Indirect Left-recursive

Given the grammar (Uppercase alphabet is non-terminal, lower-case alphabet is terminal), how to find FIRST set? A -> mB | CD B -> CBn | epsilon C -> pA | epsilon D -> q This is NOT a ...
  • 1
0 votes
1 answer
84 views

Is the language $L = \{0^i 1^j | i \ne 2j\}$ context free?

I have been trying to find a a CFG for this language generated. I came to the conclusion that I need three parts When $i \le j$ When $j < 2j < i$ When $j < i < 2j$ I was able to come up ...
2 votes
0 answers
130 views

Determining when a substring has a unique parse forest

Given an arbitrary (potentially ambiguous) context free grammar $G: \mathbb{G}$, and string $\alpha: \Sigma^\ast$, is there a decision procedure that returns whether appending and/or prepending ...
0 votes
0 answers
40 views

Methods of eliminating ambiguity in CFG

I am looking for all possible ways to find and eliminate ambiguity in CF grammar. Please share your knowledge or opinion (preferably you will indicate the literature so that I can familiarize myself)....
0 votes
0 answers
37 views

What should be the order of eliminating empty rules and unit rules when converting context free grammar to chomsky normal form?

Let's say that we have a context free grammar G, which is not in chomsky normal form, and we need to convert it to chomsky normal form. The steps involved in the conversion are as follows: Add a new ...
0 votes
1 answer
19 views

Do Left regular grammar describe a language containing the reverse of the strings described by the right regular grammar for another language?

Let's say that we have a regular language $L_1$ that is described by a right regular grammar. Now, assume we have a left regular grammar, can we describe the same language $L_1$ or would the left ...
0 votes
0 answers
19 views

Write grammar that produces a^2^i, for i>0 [duplicate]

How to write grammar for that language: $$ a^{2^i}, i>0 $$. Anyone could help?
0 votes
1 answer
26 views

In Context free languages, is it okay to substitute multiple same variables at the same time?

Let's say we have the following context free grammar: $S \rightarrow a \\ S \rightarrow SS$ And we do the following two "derivations" for the same string: aaa: $S \rightarrow SS \rightarrow ...
1 vote
1 answer
32 views

How can dfa have more than one sink state? Isn’t it the same state?

I can’t understand How can dfa have more than one sink state? Isn’t it the same state? Maybe there is some examples
  • 11
1 vote
0 answers
45 views

What is the formal definition of a combinational logic?

Question Background A finite-state machine can be defined as a 5-tuple as follows (Sipser, pg. 35): The image below (taken from the Wikipedia article on combinational logic) seems to suggest that ...
0 votes
1 answer
36 views

Convert regex for comma separated value to CFG grammar

I have the following regex that I'm trying to convert to a CFG: e|a(,a)* (e representing the empty state). Basically I want to ...
2 votes
1 answer
22 views

Duplicate rules in CFG

Suppose I have the following CFG that I would like to bring to CNF S -> TA | bA | Ab | b A -> Aa|a T -> Ab Then I have two options to get rid of the ...
  • 155
0 votes
1 answer
50 views

Simple description of the LR(0) table generator algorithm?

I have just implemented a parser on the relational database. Parsing is done with recursive query. Note: one commenter was misled by the word "recursive" before "query" to think &...
0 votes
1 answer
43 views

Why Regular Grammar is Left/Right Linear?

From the definition I know that regular grammar should be Left/Right Linear (ie it should have variable on Left/Right side of each production rules) But, my question is why it is mandatory? Can't we ...
1 vote
1 answer
88 views

How to remove ambiguity from the grammar?

I want to remove ambiguity from the grammar below: S → ABC A → abA | ab B → b | BC C → c | cC I have removed left recursion and left factoring and obtained the grammar as follows: S → ABC A → abA' A' →...
0 votes
1 answer
48 views

Why the Following Grammars Are Not in CNF

I am reading the book "Automata, Formal Languages, and Automata" written by Dr. Emre Sermutlu and in page 153, it is stated that the following grammars are not in Chomsky Normal Definition (...
1 vote
0 answers
44 views

How does ANTLR4 handle optional rules?

Are the following two stat rules equivalant? stat : 'if' expr 'then' stat ('else' stat)? ; ...
  • 9,379
0 votes
0 answers
29 views

How to prove the unambiguous of the grammar?

My question is the method to prove the grammar that is unambiguous. There may be no general method to prove it, but I want to know the the proof techniques. For example, $E\rightarrow +EE\ |\ *EE\ |\ -...
  • 1
0 votes
0 answers
16 views

The maximal choice smallest grammar algorithm. Is this an exact algorithm or an approximation?

When we speak of a variable, sometimes we will mean the string it expands to, and other times, the variable itself. Let $t \leqslant s$ mean substring. Take the string $s = a^6$. Then its ...
0 votes
0 answers
28 views

An ingenious exact smallest grammar algorithm for strings over a single letter, $s \in \{a\}^*$. First enumerate the start rules up to commutation

Take $s = a^{10}$ for our example string. Compute the set of all potential grammar reducing variable-rules: $$ A \to aa \\ B \to aaa \\ C \to aaaa \\ D \to aaaaa $$ There is always exactly $\left\...
0 votes
1 answer
24 views

What context-free grammar recognizes a list of numbers 1 - N in order?

I'm looking for a context-free grammar that recognizes precisely the numbers 1 - N in order: ...
0 votes
0 answers
57 views

Grammar for prime length strings

How do we write an unrestricted grammar for $$L = \{a^n \ | \ n \ \text{is prime}\}$$ I know that $L$ is neither regular, nor context-free. Also, I know how to build a Turing Machine for $L$. The idea ...
  • 141
0 votes
2 answers
66 views

Context free grammar for $L= \{0^i1^ic0^j1^j | j = i+1 \}$

Description This is an exercise for Formal Language course, I'm asked to find a grammar for language: $L = \{ 0^i1^ic0^j1^j | j = i+1 \}$ As an example: 01c0011 can be generated using this language, ...
0 votes
1 answer
62 views

Find the language generated by the Context Free Grammar

I am trying to find the language generated by this context-free grammar S → aSb | bbY | Yaa Y → bY | aY | ε I understand that one way to solve is this to find set ...
1 vote
0 answers
43 views

minimum number of non-terminals so that for all context-sensitive languages there is a non-contracting grammar

Every context-sensitive language $\subseteq \Sigma^* = \{a,b\}^*$ can be expressed using an essentially non-contracting grammar. With just one non-terminal symbol, we can't express all context-...
0 votes
0 answers
47 views

context free grammar for ${\{0^i1^j0^k1^l0^m \mid i, j, k, l, m \ge 0, i \le k\text{ or }j = m\text{ (or both)}\}}$

I'm trying to come up with a context free grammar for the following language: $${\{0^i1^j0^k1^l0^m | i, j, k, l, m \ge 0, i \le k \text{ or } j = m \text{ (or both)}\}}$$ I'm able to come up with ...
0 votes
1 answer
384 views

BNF and EBNF Syntax for while loops in C#

Given the programming language C#, how would I be able to write the BNF and EBNF grammar syntax of its while loop? After trying to search and understand more, I got this as my BNF grammar for while ...
0 votes
1 answer
30 views

Grammar where tokens can be transmuted

I have a grammar which is mostly LL(1), save for the fact that some tokens may be promoted to larger integer types. For example, let take the following grammar <...
1 vote
1 answer
49 views

Minimal-length strings which are substrings of no string in a given CFL

Is there an algorithm for enumerating a sequence of minimal-length substrings composed of terminal symbols within some CFG which are not substrings of any string in the language defined by that CFG? ...
0 votes
0 answers
30 views

Find a context free grammar for $0^n10^m1$, where n is even and m is odd

Let $$L_1 = \{0^n10^m1 | n, m \in N \text{ where n is even and m is odd} \}$$ I tried to build a cfg but I am not sure if it right or if it is the simplest solution. $$ G_1: V = {S}, T = \{0, 1\}$$ ...
0 votes
1 answer
54 views

Greibach Normal Form: Proof every sentential form is of the form xy with x terminals and y variables

For any grammar in Greibach normal form, every sentential form obtained from S by a partial left-most derivation is of the form xy with x terminals and y variables. I think that this can be proven ...
  • 89
2 votes
1 answer
70 views

What role does an asterisk serve in Backus–Naur Normal Form?

Suppose that you were reading some production rules for a context-free grammar in Backus–Naur Normal Form What does the asterisk (*) mean? In the example below, ...
0 votes
1 answer
56 views

How can we escape the pipe character in Backus–Naur Normal Form?

Suppose that you were writing down the syntax rules for something like C++ as a context-free grammar in Backus–Naur Normal Form How can you distinguish between the pipe character as symbol in C++ or ...
0 votes
0 answers
42 views

What is an example of some production rules which would allow parentheses, curly braces, and square-brackets to be interchangeable?

In computer programming, there are many different ways to write a for-loop. Some examples are shown below: ...
4 votes
1 answer
112 views

Formal grammar of MIU system

The MIU system, famous from Douglas Hofstadter, is a semi-thue system with the following rules: Xi → Xiu mX → mXX XiiiY → XuY XuuY → XY and a start axiom "mi" I have tried to find a formal ...
  • 143
0 votes
0 answers
16 views

Canonicalizing Arbitrary EBNF Expressions

From what I understand, LL and LR parsing require a grammar to be in "canonical form", i.e. only productions of the form A -> b1 b2 ... bn, where ...
1 vote
1 answer
164 views

determining whether a context-free language is regular

I was wondering how to determine (with proof) whether the context-free language generated by the following context-free grammar $G$ is regular, where $S$ is the start variable and $a$, $b$ are the non-...
1 vote
1 answer
32 views

if $RA$ is context-free, is $A$ context-free?

If $RA$ is context-free for a regular language R, is $A$ context-free? I think this statement is true. Let G be the CFG given by the rules $S_0\mapsto LA_1, S\mapsto LA_1, A_1\mapsto SA_2 | RS | 1, ...
0 votes
1 answer
38 views

prove that the unique language $A$ such that $AB$ is context free for all languages B is the empty set

Prove that the unique language $A\subseteq \Sigma^*$ such that $AB$ is context free for all languages $\subseteq \Sigma^*$ is the empty set. If $A$ is not the empty set, there should be a way to ...
4 votes
1 answer
290 views

What are the languages produced by context free-grammars with backspace?

If we add backspace to the output alphabet, are all the languages produced still context-free? (If not, then what are they?) The word (a, b, c, Backspace, Backspace), for example, gets interpreted as ...
0 votes
0 answers
24 views

Given an instance of a HORN-SAT problem with at most 3 literals per clause, what context-free grammar is equivalent to deciding the problem?

Given an instance of a HORN-SAT problem with at most 3 literals per clause, what context-free grammar is equivalent to deciding the problem? For example, here are some HORN clauses: ...
0 votes
1 answer
42 views

Proving grammar equivalence in simple grammar (generate any sequence of three characters)

Goal is proving grammar equivalence Upper-case symbols are non-terminal. Lower-case symbols are terminal. The start symbol is S. A grammar production rule is non-...
3 votes
2 answers
1k views

Is it always possible to order grammar rules so that all the symbols on the left will be contained on the right in a previous rule?

This is about unrestricted grammars Assume S is the start symbol. Assume 1 and 0 are ...
1 vote
1 answer
207 views

Prove a subset of a regular language is regular, context-free but not regular or not context free

I've been tasked with solving this problem, but I'm not sure where to begin: Let $L$ be a context-free language. $L'$ contains all the words that belong to $L$ which can't be defined as $z=uvwxy$, ...
0 votes
0 answers
70 views

Can the leaf nodes of a parse tree be labeled by a variable, a terminal, and the empty symbol; or only a terminal and the empty symbol?

When you are deriving a string using a context-free grammar (CFG), you start with the start symbol and at the right side you have combinations of variables (non-terminals) and terminal symbols. Let's ...
  • 355
2 votes
1 answer
147 views

Formal language rewrite rules: strange notation

I'm reading "Program=Proof" by Samuel Mimram, and they use a notation for defining a formal language that I'm not familiar with. Here is how "Program=Proof" defines a formal ...
1 vote
3 answers
254 views

How to prove the language of words $a^ib^jc^k$ where $\min(i,j)\le k\le\max(i,j)$ is not context-free?

I want to prove that $\mathcal M =\{a^ib^jc^k \mid \min(i,j)\le k\le\max(i,j)\}$ is not a CFL. Using the pumping lemma, let $p$ be the constant, then I choose $w=a^pb^pc^p$. When I separate to cases, ...
  • 239

1
2 3 4 5
25