Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
1 vote
1 answer
30 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, ...
user avatar
0 votes
1 answer
13 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 ...
user avatar
0 votes
0 answers
14 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: ...
user avatar
4 votes
1 answer
85 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 ...
user avatar
  • 141
0 votes
0 answers
14 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 ...
user avatar
1 vote
1 answer
56 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-...
user avatar
1 vote
1 answer
26 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, ...
user avatar
0 votes
1 answer
29 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 ...
user avatar
4 votes
1 answer
268 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 ...
user avatar
0 votes
0 answers
19 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: ...
user avatar
0 votes
1 answer
38 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-...
user avatar
2 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 ...
user avatar
1 vote
1 answer
43 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$, ...
user avatar
0 votes
0 answers
33 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 ...
user avatar
  • 345
2 votes
1 answer
120 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 ...
user avatar
1 vote
3 answers
137 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, ...
user avatar
  • 241
0 votes
0 answers
26 views

LR parsing and soft keywords

A lot of modern program languages these days allow for keywords to be used for variable names, function names and class names. They call these keywords soft-keywords. Only if the soft-keyword is used ...
user avatar
  • 217
1 vote
1 answer
50 views

is there a non-context free language A such that A1 is context free?

Is there a non-context free language A over the alphabet $\{0,1\}$ such that $A1 := \{a1 : a\in A\}$ is context free? I was thinking of the language $A = \{0^n 1^{n-1} : n > 0\}.$ Unfortunately, ...
user avatar
1 vote
1 answer
41 views

Is $\{x2y : |x| = |y|, x\in A, y\in\{0,1\}^*, d(x,y) = k\}$ context-free for some infinite regular language $A$?

For two equal-length binary strings $x$ and $y$, let $d(x,y)$ denote the Hamming distance. Prove or disprove: there exists a positive integer $k$ such that the language $\{x2y : |x| = |y|, x\in A, y\...
user avatar
1 vote
2 answers
54 views

Show that the Hamming distance of $wx$ and $xw$ cannot be 1

Let $w$ and $x$ be two binary strings. Show that the Hamming distance of $wx$ and $xw$ cannot be 1. I think one approach is a proof by contradiction. I was thinking of explicitly writing out $w = w_1\...
user avatar
0 votes
1 answer
55 views

Prove or disprove that $\{xc o(x) :x \in A\}$ is context-free, where A is a regular language

Suppose o is a map on strings to strings. For every language R, we let $o(R) := \{o(x) : x \in R\}$. If o(R) is a regular language for every regular language R, then prove or disprove that the ...
user avatar
0 votes
3 answers
136 views

Find a Context-Free Grammar for $L = \{a^wb^xc^yd^z | w + x = y + z\}$

I have to find a CFG for the given expression: $L = \{a^wb^xc^yd^z | w + x = y + z\}$ This is what I've tried so far: S -> aSd | B | ϵ B -> bBc | ϵ It works for expressions like: aabcdd, ...
user avatar
-2 votes
1 answer
47 views

expression/pattern for language where product of number of 0s and 1s is even

I am trying to solve one of the sample test problems in which I have to write an expression/pattern for the following language: $\{w \in \{0, 1, 2\}^*: {\#}_{0}(w) ∗ {\#}_{1}(w) \text{ is even}\}$ I ...
user avatar
0 votes
1 answer
51 views

find LR(1) items of the first state

I need to calculate the LR(1) items of the following grammar: S -> E E -> E + T E -> T T -> ID T -> ( E ) I can not even calculate the first group {[...
user avatar
  • 3
0 votes
2 answers
54 views

LR(1) grammar that can not be transformed an LL(1) grammar

Looking for an example of a LR(1) grammar that can not be turned into an LL(1) grammar that parsers the same language.
user avatar
  • 217
2 votes
0 answers
68 views

Is the language $L = \{{a^{2n+1}b^{m+2}a^n | m \neq 2n}\}$ context-free?

$L = \{{a^{2n+1}b^{m+2}a^n | m \neq 2n}\}$ I tried to split $L$ in 2: when $m > 2n$ and $m<2n$, however both resulting languages are not context-free, so I did not find out anything about $L$. ...
user avatar
-3 votes
1 answer
90 views

Prove a stronger version of the pumping lemma for context-free languages

Let $L$ be a context-free language. Prove that there exists integer $p>0$ such that $ \forall z\in L $ such that $ |z|\ge p $, there exists a partition $ z=uvwxy $ such that $|vwx|\le p$ $|vx|\...
user avatar
0 votes
2 answers
79 views

Design a CFG for $L=\{ w \in \{ 0,1 \}^* \}$, where $w$ contains at least three ones

$L=\{ w \in \{ 0,1 \} \}$ where $w$ contains at least three ones Here is one solution for the productions: $S \to A1A1A1A$ $A \to 1A | 0A | \epsilon$ However, now I have a question. Could I modify the ...
user avatar
  • 155
0 votes
1 answer
87 views

Context-free grammar for language $L = \{u \in \{a, b\}^* \mid |u|_a = |u|_b\}$ [duplicate]

I need to find the production rules for the following language: $L = \{u \in \{a, b\}^* \mid |u|_a = |u|_b\}$ Well, the first thing I could come up with is $S \to aSb | \epsilon$ But this only covers ...
user avatar
  • 155
0 votes
0 answers
38 views

Union of two context-free grammars and their productions

Is it possible to create an union of two context-free grammars? I found a PDF material from the university of Iowa where they claim that it's possible but I just don't know how. They had that for ...
user avatar
  • 155
1 vote
1 answer
72 views

Context-free grammar for $L=\{ a^nb^m | n \le m+3 \}$

I'm having problems determining the productions for a CFG describing the language $L=\{ a^nb^m | n \le m+3 \}$ where $n,m \ge 0$ I'm very new to this so this example might be a little harder, but ...
user avatar
  • 155
3 votes
0 answers
32 views

Is there an alternative for the formal language theory that could be used for flowchart diagrams?

I am creating a tool for validating, parsing and interpreting flowchart diagrams on diagrams.net, and it is neccessary to give users an opportunity to define a set of rules for the diagram. So, in the ...
user avatar
0 votes
0 answers
55 views

Defining grammar for $L=\{a^ib^ic^jd^j| i \ge j \ge 0\}$

I need to define a grammar for $L=\{a^ib^ic^jd^j| i \ge j \ge 0\}$ as I wasn't told about any restrictions for the grammar, e.g context-free or context-sensitive, I assume any derivation rules can be ...
user avatar
0 votes
1 answer
36 views

When is a grammar ambiguous or When is a grammar not ambiguous?

I was looking at an example of grammar from the website: grammer example which is as follows: S → aB / bA S → aS / bAA / a B → bS / aBB / b I believe they forgot to write: A -> a Next, we are going ...
user avatar
0 votes
1 answer
75 views

Decidability of a context free Grammar

Say that a Context Free Grammar is red when it accepts every word of length 3 that begins with a, and extremely red when it accepts every word that begins with a. Is redness decidable? or Semi ...
user avatar
1 vote
1 answer
54 views

Language generated by $S \to aAb|Sb$, $A \to aAb|ab$

Let $G = (\{A,S\}, \{a,b\}, S, P\}$ be the grammar with the following productions: \begin{align} & S \to aAb | Sb \\ & A \to aAb | ab \end{align} What is the language $L(G)$ generated by the ...
user avatar
3 votes
1 answer
77 views

What is the formalism used to describe optional arguments called?

Most command line tools have an usage described by using square brackets for optional parts and just writing out required parts (like in regexes) for example: foo [opt1[opt2...]] req1 req2 [opt3...] ...
user avatar
-3 votes
1 answer
52 views

What's grammar for a^n b^n c^n d^n

What wiil be grammar rules for the language L={a^n b^n c^n d^n; n>0}
user avatar
2 votes
0 answers
22 views

Finding a Context Free Grammar for Different No. of a and b AND Different No. of b and c [duplicate]

The question is from my homework: Is the language $\{a^ib^jc^k\mid i,j,k\geq0\land i\neq j \land j \neq p\}$ a context-free language (CFL)? If yes, please provide a context-free grammar for it. I ...
user avatar
0 votes
1 answer
40 views

Finding a context free grammar (CFG) for a non-context free language (CFL) a^n b^n c^n

It is known that the language $\{a^nb^nc^n|n\geq0\}$ is not context-free (we can prove it using the pumping lemma, as shown here: Is $a^n b^n c^n$ context-free?). Yet, this answer claims it has found ...
user avatar
  • 1
0 votes
0 answers
19 views

Can you recommend some materials on Turing Machine?

I need exercises with answers to practice building Turing machines. Books, online resources etc. Can anyone recommend something?
user avatar
1 vote
1 answer
35 views

Constructing an unrestricted grammar for XWX, where W is the reverse of X

I'm trying to construct an unrestricted grammar for strings of the form XWX, where W is the reverse of X, over the alphabet {a, b}. I think I can apply similar logic to the a^nb^nc^n solution (below), ...
user avatar
2 votes
1 answer
64 views

How to identify Context-Sensitive Grammar?

Context-Sensitive Grammar is defined as a 4 tuple G = (V, Σ, R, S) where: V is a finite set of elements known as variables. Σ is a finite set of elements known as terminals V ∩ Σ = Null (empty set) S ...
user avatar
  • 25
1 vote
1 answer
44 views

Prove/Refute that $L=\{w\$x^R \ |\ x\ is\ a\ substring\ of\ w\}$ is a regular language

I was solving some exercises about CFL from past years' homework and faced this question. Question: Given the language $L=\{w \# x^R \ | \ x\ is\ a\ substring\ of\ w\}$, prove/refute if it's regular ...
user avatar
-1 votes
1 answer
82 views

Context Sensitive Grammar for $x \# x^R \# x$

This language is given. $L = \{\; x \# x^R \# x \mid x\in \{a,b\}^*\;\}$ I have to figure out a context sensitive grammar for it. I've tried several rules already but it's hard to make a copy of the ...
user avatar
0 votes
0 answers
43 views

Languages with number of $a$'s a perfect square

Is there any finite automata ((N/D)FA, NPDA, DPDA, or any variation of a Turring Machine) that can accept the following language: $\{s \text { is a string over } \{a,b\} \text { such that the number ...
user avatar
  • 141
0 votes
0 answers
55 views

Why is the LR(1) automaton deterministic?

Let $G = (V, \Sigma, P, S)$ be an LR(1) grammar. We can define a non deterministic $\lambda$-automaton[1] as follows. First of all we extend the grammar with an additional symbol $S'$ which will be ...
user avatar
0 votes
1 answer
122 views

How to find context sensitive grammar for words like ww?

I'm studying formal languages and automata, and on the section of learning how to find productions that generates the grammar, I've done some exercises pretty well and was able to do some of the ...
user avatar
0 votes
1 answer
57 views

How would my parsing functions look for this grammar?

Suppose we have the grammar $$S \to aA | BA $$ $$A \to a | bB | \epsilon $$ $$ B \to cB | d$$ I know that I need to write four different functions in order to parse this grammar. They are ...
user avatar
  • 3
3 votes
2 answers
133 views

LALR(1) grammar for simple math parser

I am trying to write a simple parser for a small calculator project, that should be able to parse e.g. the following inputs: ...
user avatar
  • 33

1
2 3 4 5
24