Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
0
votes
1answer
24 views

What kind of Grammar could this be

I am trying to sort Grammar into the Chomsky Hierarchy and I can do so for most of my examples but I am stumped by the following one: bX -> abY which Type of ...
3
votes
1answer
31 views

Minimizing DFA built on set of words

A set of English words is given. Is there linear or sublinear algorithm to build minimal DFA for the given dictionary? I tried different approaches, and they all were concerned with building Trie and ...
4
votes
0answers
52 views

Reference on relating Post systems to string rewriting systems and formal grammars?

wikipedia states: Every Post canonical system can be reduced to a string rewriting system (semi-Thue system). [...] It has been proved that any Post canonical system is reducible to such a ...
2
votes
1answer
32 views

Set notation of a grammar

Say I have a grammar e.g, $$\begin{align}S&\to AB\mid abc\\ A&\to aAb \mid \lambda\\ B&\to bBa \mid ba \end{align}$$ Now it is obvious the notation for this would be something like, $$L(...
10
votes
3answers
2k views

Representing “but not” in formal grammar

I just came across the following grammar definition: CommentChar ::       SourceCharacter but not LineTerminator But for discussion, I'll present this similar ...
0
votes
1answer
40 views

Table-Driven Lexer and the Classification Table

I'm trying to implement a compiler for a custom language as part of an assignment. I am still trying to figure out how to build the lexer. From what I understand, for a table-driven lexer, we have 3 ...
2
votes
4answers
12k views

Converting context-free grammar to chomsky normal form

I'm trying to prove that the following CFG can be converted to a CNF: S -> aAB A -> aAa A -> bb B -> a Here below is how I've managed so far: Step 1:...
4
votes
2answers
905 views

Generating random words by grammar

A bit of context I was writing a parser for a grammar, and for testing purposes I come up with idea to generate some random inputs. The grammar I was dealing with was much more complicated, in this ...
0
votes
1answer
77 views

How to determine valid handle for given bottom up parser?

I came across following question: Consider the grammar: $E → E + n\text{ | }E × n\text{ | }n$ For a sentence n + n × n, the handles in the right-sentential form of the reduction are (...
0
votes
2answers
43 views

Formal grammar with constraints on the number of each symbol

I have a language where each type of symbol is only allowed a particular number of times, but the order isn't important. For example, lets say there are three symbols $a, b, c$, and a valid string in ...
-2
votes
0answers
24 views

Right-linear and left -linear Grammar

Could some explain what's the difference between right-linear grammar and left-linear grammar? Maybe on this example: $L:=\left\{w \in\{a, b\}^{*} | w \text { does not contain the subword abaab }\...
0
votes
1answer
24 views

Determining recursive enumerability of given languages

I came across following problem: $L=\{M$ is a turing machine $M$ accepts two strings of different length $\}$ $L=\{M$ is a turing machine $M$ accepts atleast two strings of different length $\}...
1
vote
2answers
45 views

Is my grammar correct and context free?

I have this language $L = \{a^{n}b^{3n}c^{2m} : m,n \ge 1\}$. I have to determine a free context grammar that generates L. Looks easy BUT i have a question about the grammar I found. First things ...
2
votes
4answers
3k views

DFA accepting strings with at least three occurrences of three consecutive 1's

The problem states the following: Draw a deterministic finite automaton (DFA) accepting strings containing at least three occurrences of three consecutive 1's on alphabet $\Sigma=\{0,1\}$ with ...
3
votes
3answers
678 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 ...
0
votes
1answer
27 views

How to create CFG for $L := \{x| \#_0(x) \text{ is even and } \#_1(x) \text{ is odd}\}$

Create an CFG for all strings over {0, 1} that have the an even number of 0’s and an odd number of 1’s. Also, I have a hint HINT: It may be easier to come up with 4 CFGs – even 0’s, even 1’s, odd 0’s ...
1
vote
2answers
185 views

Does left factoring CFG make it unambiguous?

I came across following problem: If the CFG is left factored then it must be Unambiguous and Not left Recursive. TRUE/FALSE? I have many thoughts about this. But I feel they are somewhat ...
-1
votes
1answer
27 views

Grammar for the following language: L = {$a^{k}$$b^{n}$$a^{m}$ : m,n,k $\in$$ N^{+}$ $\land$ m + k $\geq$ n}

I'm trying to create a grammar (having the highest type) for the language: L = {$a^{k}$$b^{n}$$a^{m}$ : m,n,k $\in$ $N^{+}$ $\land$ m +k $\geq$ n} I'm not finding any good approach for it. Hints ...
0
votes
1answer
38 views

CFG for $L=\{ \omega \in \{ a,b,c,d \}^* : |\omega|_a = |\omega|_b \}$

Given the language: $$ L=\{ \omega \in \{ a,b,c,d \}^* : |\omega|_a = |\omega|_b \} $$ I propose the following grammar: $$ \begin{align*} S &\to \varepsilon \mid aSbS \mid bSaS \\ S &\to ...
0
votes
1answer
32 views

Is this grammar LL(1) grammar?

Is this grammar LL(1)? Would it be a problem that S can be both E/S and E? S -> E / S S -> E E -> letter E -> ‘ S ’ Can it derive ‘a / e / ‘g / s’ ’...
1
vote
2answers
249 views

There exists an algorithm to find grammar of complement of a function?

I'm wondering if there exists an algorithm to solve the following problem: Given a grammar $S$ of a context-free language $\mathcal{L}$, find a grammar $S'$ such as $L(S) = L(S')^c $. I note ...
4
votes
2answers
434 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 ...
1
vote
2answers
41 views

Context-free grammar for ${a^n b^n a^n}$

I am trying to figure out a formal grammar for the above language. This language describes palindromes, so it is context-free, if I am not wrong. I came up with a context-sensitive grammar, but I can ...
0
votes
0answers
22 views

How to include both precedence and associativity in following grammar?

For the following grammar, how can I include both precedence and associativity of operators: S -> S|S S -> S.S S -> S* S -> (S) S -> a|b Note: In the first rule ...
0
votes
0answers
20 views

Find equivalent LL(1) grammar

There is sample question to calculate equivalent LL(1) grammar for below grammar: $S \rightarrow S b$ $S \rightarrow S d$ $S \rightarrow c S$ $S \rightarrow c c a$ At first step, ...
0
votes
0answers
21 views

Dangling Else Ambiguous Grammar

How is the following grammar ambiguous stmt -> if expr then stmt | matched_stmt matched_stmt -> if expr then matched_stmt else stmt | terminal
3
votes
2answers
158 views

If L = {xy | |x| = |y|, x=y} is not Context Free, then what about L = {xy | |x| = |y|, x!=y}?

I know that, when x = y, then it's not Context Free. This is because, the first letter of y cannot be matched with first letter of x, which is at the bottom of the stack. But, a link of Show that { ...
0
votes
0answers
29 views

Is this correct transformation of a grammar to one without left recursion?

So the last few days I am writing a compiler for a subset of C language by given grammar for a class at university. I encountered this problem and then I realized I need to remove left-recursion in my ...
1
vote
1answer
54 views

Proving that the set of grammars generating L or L complement is undecidable

Let $X$ be a regular language, I need to prove that either $\{G \mid L(G) = X\}$ or $\{G \mid L(G) = \overline{X} \}$ is undecidable using the following hint: Use reduction to absurdity supposing that ...
0
votes
2answers
51 views

Is this correct grammar definition of Backus-Naur form?

I've been given a grammar definition of "Simple C language" in Backus-Naur to write a compiler for a class assignment. I've been trying to implement the parser for some time now and I just can't move ...
0
votes
1answer
57 views

What does {a,b}* for DFA's mean?

For instance when the question contains $\{a,b\}^*$ does this mean that the DFA must have at least one $a$ and one $b$ on top of whatever conditions it has? For example a DFA that accepts $\{w \in \{a,...
0
votes
0answers
11 views

Detect a class of a grammar having its DSL AST

I have a grammar for some language written in some DSL for writing grammars, and this DSL implements EBNF. I have an AST for the description of a grammar in the DSL. How can I detect the minimal class ...
1
vote
1answer
45 views

Proof that language is not regular. $L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$

I'm trying to proof that the following language is not regular using pumping lemma. $L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$ I started by stating that: $|w\bar{w}| =...
2
votes
1answer
344 views

What's 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 ...
14
votes
2answers
2k views

What is an IELR(1)-parser?

I try to teach myself the usage of bison. The manpage bison(1) says about bison: Generate a deterministic LR or generalized LR (GLR) parser employing LALR(1), IELR(1), or canonical LR(1) parser ...
10
votes
1answer
330 views

Shift-resolve parsing - questions

I've recently came across a paper describing the parsing technique mentioned in the title. Unfortunately, the terminology used in said paper is somewhat beyond my comprehension, so I've been ...
0
votes
0answers
56 views

I´m having problems with this Context Free Grammar

I am not able to convert the following language to a Context Free Grammar. The major problem is how to pump both "sides" of the word to obtain same number of 0s and 1s, but, without creating a series ...
0
votes
1answer
22 views

Textbook for understanding formal grammars

I am looking to understand the Chomsky Hierarchy. I've read some textbooks that touch on formal grammars (textbooks on computability, which relate automata to specific sets of formal grammars, notably ...
1
vote
1answer
374 views

Proof that the grammar is LL(2)

I am given the following grammar: $ S \rightarrow AabAba \\ A \rightarrow a | \epsilon $ and I have to prove it is LL(2). I know what LL(k) means - one can choose a production based on k characters ...
0
votes
1answer
71 views

How to convert the left recursive grammar into right recursive grammar

I have a grammar: $A\rightarrow Aa|bB|c$ The above is the left recursive grammar. I understand that I have to remove the string "Aa" from the above grammar or to convert it into the form "aA" to ...
1
vote
3answers
538 views

Context-free grammar for binary words

I am supposed to create CFG for this languague: $L= \{w : w \in \{a, b\}^*, |w_b| = 3k, k \geq 0 \}$ where $|w_b|$ is count of terminals $b$ in $w$. For example: aa - OK, no 'b' abb - wrong, only ...
2
votes
1answer
216 views

Negative lookahead in LR parsing algorithm

Consider such a rule in grammar for an LR-family parsing generator (e.g YACC, BISON, etc.): Nonterminal : [ lookahead not in {Terminal1, ..., TerminalN} ] Rule ; ...
0
votes
1answer
89 views

Why LL(1) grammar generate all regular languages?

I came across following: Every regular language has right linear grammar and this is LL(1). Thus, LL(1) grammar generates all regular languages. I tried to get that. Definition: Right linear ...
0
votes
1answer
34 views

Adding constraints in grammar for Grammatical Evolution

I'm trying to use Grammatical Evolution for creating trading strategies. Each sentence in the grammar when evaluated gives a weight matrix of size n x p . (n is the length of backtesting period and p ...
1
vote
2answers
116 views

CFG - Left factoring in recursive nested productions

I'm attempting to convert a CFG into an LL(1) grammar for predictive parsing in a compiler. I've been able to left factor and eliminate left recursion and ambiguity for every case in the grammar, with ...
0
votes
1answer
15 views

Ambiguous Grammar demostration exercise

Hi im stuck on an exercise of ambiguous grammar. I need an example that shows that this grammar is ambiguous. The grammar is defined as follows: $$S \rightarrow aT | bR$$ $$R \rightarrow a | aS | bRR$...
2
votes
2answers
93 views

Grammar with fewest variables

I am looking over a past exam for a theory of computation class I am taking, and unfortunately no solutions are provided. I am stuck on this question, and would greatly appreciate any help or hints. ...
2
votes
1answer
33 views

How does $LL(n)$ languages compare with $LR(0)$, for $n>0$?

In the context of languages (not grammars), I know following: $LL(0) \subset LL(1) \subset LL(2) \subset \cdots \subset LL(k)$ $LR(0) \subset SLR(1) = LALR(1) = LR(1) = SLR(k) = LALR(k) = LR(k)...
1
vote
1answer
35 views

How to write grammar production rules to describe recursive structures?

I'm trying to describe a data structure by production rules. The structure is recursive; say a list of type $A$ made of elements of type $A$ or $B$. Writing the grammar, I build this: $(S \...
1
vote
1answer
39 views

Find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$

I want to find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$ I've tried the following: $G=(V,\Sigma,R,S)$ with $\Sigma=\{a,b,c,\lambda\}$, $V=\{S,B\}$, $S=S$ and $$R=\{S\to \...

1
2 3 4 5
20