# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

1,032 questions
Filter by
Sorted by
Tagged with
31 views

### Express L(G) in set notation

Consider the G grammar below. S ->aSa|A A ->bAb|B B ->ccB|λ Just want to express L(G) in set notation. Could some give me some ideas?
30 views

### Is this grammar in Backus–Naur form?

I'm a newbie and a paper I'm reading specifies the following grammar: ...
450 views

49 views

### Is every language described by a grammar?

I read the following argument showing that not every language is described by a grammar: For a fixed alphabet $\Sigma$ and variables $V$ there are uncountable many languages over $\Sigma$ since the ...
23 views

### If a grammar G is left and right regular, why $||L(G)|| \leq ||P||$?

I was studying automata theory and formal languages and came across this question: If a grammar $G$ is left and right regular, why $||L(G)|| \leq ||P||$ ? I've searched the theory but I am missing ...
70 views

### Enumerator for Word and Halting Problem

in theoretical computer science I learned for every recursive enumerable language there would be an enumerator and a grammar. So since word problem and halting problem are recursively enumerable, I ...
41 views

### Is there any official terminology about something like double quotes “” grammar?

In many programming language string is a token. For example: ...
60 views

### How to design a formal grammar to convert EBNF description to a list of CFG production rules

I would like to write a grammar to convert EBNF description to a list of CFG production rules, instead of an algorithm. Can CFG production rules is generated from an EBNF description by a rewrite ...
47 views

### Is there a way to map the concatenation operation over strings to the addition operation over $\mathbb{N}$

Given an alphabet, say $\Sigma = \{0,1\}$, I can make a one-to-one mapping from all possible strings $x \in \Sigma^*$ to $\mathbb{N}$. This could be done by ordering $\Sigma^*$ lexicographically and ...
97 views

41 views

### Regular expression for a palindrome of finite length?

I have a language $$L = \{ww^R, w \in \{ab\}^5\}$$ I know this is a regular language because it is finite (since w can only be of length 5). I want to prove it's a regular language, so I'd create a ...
111 views

### Why is this language a regular language?

Came across this in a book, and I'm wondering why the following language is regular? $$L = \{a^nww^R: n \geqslant 0, w \in \{a,b\}^3\}$$ Is it correct to say that $$\{a^n : n \geqslant 0\}$$ is a ...
37 views

### How to create a regular expression for this language?

I have a language: $$\{a^jb^k \mid j \neq k \text{ and } j \equiv k \pmod 3 \}$$ I want to prove that this language is regular. My first thought was to create a regular expression that accounts for ...
Let $G$ be a CFG in Chomsky normal form that contains $b$ variables. Show that if $G$ generates some string with a derivation having at least $2^b$ steps, then $L(G)$ is infinite. This question is ...