# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

1,041 questions
Filter by
Sorted by
Tagged with
65 views

### Is the following language is a context free grammar language?

The question is to determine whether L is a context free grammar language, what do you think?
85 views

### Unambiguous context-free grammar for strings with at least as many a's as b's

I have designed this Grammar but it is ambiguous: $$S\to aSbS \mid bSaS \mid aS \mid\epsilon$$ Would anyone help me make it unambiguous? Assume the alphabet is $\{a,b\}$.
40 views

### Given a CFG and one of its nonterminals $v$ determine if there exists a sentential form beginning with $v$?

I am supposed to find an algorithm solving the following problem: Given a CFG $\;G=(V_N, V_T, R, S)$ and a nonterminal $v \in V_N$ determine if there exists a sentential form which begins with $v$. ...
37 views

### How to generate a DFA that recognizes a non-regular Grammar

How would you convert the following grammar to a DFA that recognizes its language? \begin{align} &G = (\{S,A,B\},\{0,1\}, S, P)\\ &P\colon &&S\rightarrow A1B\\ &&&A \...
28 views

32 views

### Defining Grammar for Given Language

I'm attempting to practice for an exam and I'm having some trouble on one of the practice problems. The problem asks to identify a variety of language as regular grammar, context-free grammar, context-...
21 views

### Language of particular CFG

Let: $G = <V, \Sigma, R, S >: \\ V = \{ S,A,B,C \} \\ \Sigma = \{0, 1\} \\ R: \\ S \to CSC|A \\ A \to 0B1|1B0 \\ B \to CB|\epsilon\\ C \to 1|0$ I need to find the language (no need to ...
21 views

### Find CSG for $L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$

I am trying to find a context sensitive grammar for the type-1 language $L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$ I can construct the first part with \begin{align*} S &\to aSbB \mid B \...
9 views

### Writing a Grammar to a Language [duplicate]

is there a general method or approach to writing grammars to a language? I do not want to describe the language I have to write a grammar to as I do not want a specific answer. I am looking for ...
20 views

### What complexity class is this set of grammars? RE?

Given a grammar where every rule has the form $X \to YZ$, $XY \to Z$, $X \to a$, or $X \to \epsilon$ where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ ...
43 views

### What complexity class is this set of grammars? In between NL and P?

Given a grammar where (every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$), (($X \to YZ$) implies ($X \to ZY$)) and (($XY \to Z$) implies ($YX \to Z$)) where $X,Y,Z$ range over nonterminals ...
15 views

### What complexity class does is this set of grammars? L-complete?

Given a grammar where every rule has the form $X \to Y$ or $X \to a$ and (($X \to Y$) implies ($Y \to X$)) where $X,Y$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$...
44 views

### What complexity class is this set of grammars?

Given a grammar where every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$ where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, ...
39 views

### What complexity class does is this set of grammars? NL-complete?

The unrestricted grammars characterize the recursively enumerable languages. This is the same as saying that for every unrestricted grammar G there exists some ...
49 views

### Would the following grammar be ambiguous?

I have the grammar $S = aSbS|bSaS|\varepsilon$. When I was first looking at the problem I thought it was unambiguous. When I looked at the answer it said that it was ambiguous. The solution it gave ...
39 views

### Grammars and Parsing: Ambiguity in Sequences

BACKGROUND I am writing a grammar and parser for a domain-specific language. There is a specific form of expression that, while simple, is giving me headaches. Given terminals: "a": KEYWORD "b": ...
547 views

### Complement of a DFA without final states

Let $L_1=\{Q,\Sigma,q_0,\delta,Q\}$ be a DFA that accepts a language $L$ and where all the states are also final states. If we want a DFA that accepts the complement of $L$, we swap its accepting ...
19 views

### Grammar for $\{a^n b^m c^{n+m} \mid n,m \ge 1\}$ [duplicate]

Please help me solve this problem: Design a grammar for the language $\{ a^n b^m c^{n+m} \mid n,m\ge 1\}$.
109 views

### Is there a difference between the equivalent automaton of a grammar and an automaton which accepts the language produced by the grammar?

I have been assigned some homework in uni, related to push-down automatons (evaluated via final state, not empty stack) and context-free grammars. I have noticed that questions related to generating ...
34 views

22 views

### Build LL(1) parsing table for grammar S -> iSeS | iS | a

Task Bulid parsing table for grammar S -> iSeS | iS | a Resolve conflicts in this table and simulate parser work for word ...
131 views

### What is the relation between parsing languages and checking languages?

I have looked at a number of textbooks on computability theory. They typically have the following form: Define a language class (regular, context-free, context-sensitive, recursively enumerable) ...
37 views

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 ...
157 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 ...
945 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 ...
53 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 ...
45 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 ...
29 views

263 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 ...
28 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 ...
22 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, ...
25 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
198 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 { ...