# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

1,251 questions
Filter by
Sorted by
Tagged with
36 views

### Context free grammar $\{0^n 1^m : n,m \geq 0\}$

I just started studying the concept of context-free grammars and I find something very confusing. Watching a video I found someone tackling the problem ${0^n 1^m : n,m\geq 0}$. I thought that the ...
1 vote
39 views

### Communication complexity of Dyck language

I've been reading papers on streaming algorithms and ran across the following question which I haven't been able to answer: Consider the Dyck language $Dyck(2)$ over the alphabet $A = \{(,),[,]\}$ and ...
1 vote
16 views

### Number of DCFG parse tree nodes with respect to input length

I read the question and answer at Number of nodes of a parse tree when the Grammar is in CNF?, and I'm curious about a related matter: obviously with a unrestrained LR grammar (as opposed to CNF) the ...
51 views

### Derivation trees to show a given grammar is ambiguous

Given the grammar with productions: \begin{align} S \rightarrow aSb \mid SS \mid \lambda\\ \end{align} I would like to show that it is ambiguous. As I understand it, if you can show that some string ...
21 views

### Lambda Calculus with State

I want to define a typed domain-specific lambda calculus which can simulate the sequence execution like common programming language. I wonder how to give its corresponding BNF, can I use ...
1 vote
39 views

### Is the class of star-free languages just the complement to counter languages within the regular language class?

So I'm kind of confused as I'm not that deep into the algebraic theory of languages. The wikipedia article states: Another way to state Schützenberger's theorem is that star-free languages and ...
1 vote
19 views

### Parsing expression grammar for a language consisting of sentences with one character added or removed anywhere

Given a parsing expression grammar for a language, is there a way to make a parsing expression grammar for a new language that consists of the valid strings from the original language, plus the ...
349 views

### Why is Dyck-2 so important for the Chomsky-Schützenberger theorem?

I have read a lot of times, that models that can parse Dyck-2 are of great importance. It appears that Dyck-2 is interchangeably used like Dyck-N. Afaik the Chomsky-Schützenberger representation ...
33 views

### An elementary question about grammar

Recently, I am studying grammar in automata. And, I have few information about this subject. I have a grammar with rules $\{S\to ASA, A\to aA, A\to \epsilon\}$. Is it true if I say that $S\to aASA$ ...
63 views

### Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s

Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s. Is P' context-free? I know that for the language of ...
1 vote
31 views

### How need help to specify a grammar for arithmetic expressions

I am trying to come up with a grammar for arithmetic expressions with the following order of operations: Parentheses Factorials Exponents Functions / unary plus and minus Juxtaposition (implied ...
1 vote
72 views

### Is $L=\{1^n2^n3^m : n\neq m\}$ context free?

Is the language $L=\{1^n2^n3^m : n\neq m\}$ context free? I checked and it satisfies the pumping lemma (Right?). Does it also satisfy Ogden's lemma, or any other test for being non-context free?
50 views

### How is $\{a^m b^n c^p d^q \mid m*n=p+q\}$ context sensitive?

I have been trying to understand how the language $L = \{a^m b^n c^p d^q \mid m*n=p+q\}$) is context-sensitive? I first encountered this question here. Would be grateful if you could provide some ...
1 vote
77 views

1 vote
75 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
1 vote
55 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 ...
49 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 ...
41 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 ...