Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
3 votes
0 answers
31 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
47 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
31 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
59 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
51 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
-1 votes
0 answers
31 views

Does my solution follow the FNC for a context-free grammar?

From the starting point we have this grammar: S→AA|AB A→aBa|BbB|BabB B→abB|C C→Cc|Ac The first step is to remove empty (ε) and unitary values. From the example ...
user avatar
3 votes
1 answer
72 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
43 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
32 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
30 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
58 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
39 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
79 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
37 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
51 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
69 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
45 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
2 votes
2 answers
115 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
  • 23
0 votes
1 answer
41 views

Decidability of a given grammar if it is regular

According to my course the question "Is $L(G)$ regular?" undecidable. But I was more interested in knowing the exact algorithm or proof that makes this question undecidable. To further ...
user avatar
3 votes
0 answers
30 views

Is there a context-agnostic concept of automatic (log-)text parsing that supports human reader filtering out redundancy?

This question is about ideas I regularly think about, and I would like to know what concepts already exist. Also I am not sure at all if this really makes sense, by now it is just a crazy idea ...
user avatar
  • 131
0 votes
0 answers
29 views

How to prove a number of LR(0) states?

I have this grammar $G_n, n\ge 2$: $$\begin{align}S&\to A_iB_i, 1\le i \le n\\ A_i&\to a_jA_i\mid a_j, 1\le i\land j\le n\land j\ne i\\ \end{align} $$ How can I prove that this grammar has ...
user avatar
  • 137
0 votes
1 answer
21 views

How to prove correctness of a bidirectional converter between two CF grammars?

I have a converter between two context-free grammars which are both describing the same language but one uses infixes other than prefixes, has different symbols and sometimes switches order of ...
user avatar
0 votes
0 answers
29 views

How to count the number of nodes for a tree generated by context free grammar derivation?

Given context free grammar I use breadth first search and left most derivation rule to generate all possible words for a given language. For example: ...
user avatar
  • 287
0 votes
1 answer
79 views

Disambiguating grammar for Dyck language

Given the following simple grammar for a language that contains all strings with matched parentheses: \begin{align} &s \to ss \\ &s \to (s) \\ &s \to () \end{align} Examples: $(), ()(), (()...
user avatar
  • 287
0 votes
1 answer
16 views

Computing Earley Parsing Steps

I am trying to understand Earley parsing algorithm using an example. The grammar I use produces all the palindromes over $\Sigma=\{a,b,c\}$: \begin{align*} Z & \to S\\ S & \to a\,|\,b\,|\,c\,|\...
user avatar
  • 163
0 votes
1 answer
91 views

Remove left recursion from a grammar without necessarily removing epsilon production

Consider the grammar $$S →Aa∣b$$ $$A →Ac∣Sd∣ϵ$$ Construct an equivalent grammar with no left recursion and with minimum number of production rules. $\tag {GATE-CS-1998}$ While solving this question, ...
user avatar
0 votes
0 answers
37 views

Complexities of algorithm for generating strings of length k from CNF grammar

Question: For the code "generate_language_rec" below, explain whether the time and space complexities are Linear, Polynomial or Exponential ( find a tight upper-bound ) in $k $. Assume the ...
user avatar
0 votes
1 answer
67 views

Reduce-reduce conflict in SLR vs LALR

I was wondering if I could say any of the following is true. Given a grammar $G$, If the LALR parser has reduce-reduce conflict for $G$, then the SLR parser also has reduce-reduce conflict for $G$. ...
user avatar
0 votes
1 answer
251 views

Context free grammar for $1^n 0^m 1^k 0^p$ where $n+k=m+p$

i need to convert this CFL to CFG $$ L = \{\; 1^n 0^m 1^k 0^p \mid n\ge 2, k,m,p\ge 1, n+k=m+p\;\} $$ I am trying to solve this problem for a few days but i couldn't. Is there anyone to help me? I'm ...
user avatar
0 votes
0 answers
18 views

Find CFG for bin(n)bin(2n+3)^R

Where bin(n) is the shortest binary representation of n. First, we can see that we can rewrite it as $bin(n)bin(2(n+1)+1)^R$ which implies that the second word will always start from 1. We can also ...
user avatar
  • 1
1 vote
0 answers
26 views

How does one parse a string into an AST (Abstract Syntax Tree) directly instead of to a CST (Concrete Syntax Tree)?

I wanted to parse strings to AST data structures instead of CSTs - which introduce a lot of intermediate nodes like terminal that might not be needed. I am not sure if one first creates a CST and then ...
user avatar
0 votes
4 answers
106 views

Making a simplest possible CFG to recognize the language L = {a^i b^j c^k | i + j ≥ 2k}

The language given is $L = \{a^i b^j c^k\mid i+j \ge 2k\}$ for which I need to construct a simplest possible Context Free Grammar. I tried understanding but I could only go as far as making sense of $...
user avatar
  • 1
0 votes
0 answers
41 views

How to prove that this "priority" strategy (in ANTLR4) solves the "dangling-else" ambiguity?

As shown in this post @ stackoverflow, ANTLR4 seems able to resolve the "dangling-else" ambiguity @ wiki in the following "if-then-else" grammar by prioritizing the "...
user avatar
  • 9,179
2 votes
1 answer
49 views

How does LALR(1) parser behave compared to LR(1) paser?

In Section 4.7.4 of the book "Compilers: Principles, Techniques, and Tools" (2nd Edition), it reads: "The revised parser (LALR(1)) behaves essentially like the original (LR(1)), .... ...
user avatar
  • 9,179
0 votes
1 answer
34 views

References to deterministic time complexity of language classes

It's fairly well known that $REG \in TIME(n)$. I would like to know similar inclusions for the language classes $DCFL$ and $CFL$. I have found a variety of claims for these classes on the internet. ...
user avatar
0 votes
1 answer
32 views

Grammar where the precedence of condition operators are asymmetric with regard to assignment operators

In Unix shell programming, there's the ideom: program1 && program2 && program3 where successful completion of ...
user avatar
  • 151
2 votes
1 answer
40 views

What does $g \to \lambda$ mean in the L-System for the dragon curve?

I am playing with L-System using the wonderful tool jflap. Below is the L-System for the dragon curve in the "JFLAP book: JFLAP – An Interactive Formal ...
user avatar
  • 9,179
2 votes
1 answer
52 views

Convert a dfa to rule for a asterisk case

Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
user avatar
  • 19
-1 votes
1 answer
39 views

I can't visualize what happens when we pump v and y in pumping lemma for $a^n b^n c^n$

If you need some context-: https://www.andrew.cmu.edu/user/ko/pdfs/lecture-11.pdf around page 7. Case 1-: Say vxy contains ab So when I pump v and y, what will get pumped? And how the result would be. ...
user avatar
  • 39
1 vote
1 answer
36 views

CFG for L={a^i b^j c^i; i,j > 0}

I worked a bit on this and got this-: S->ABC A->aA/a B->bB/b C->cC/c The obvious problem here is I am unable to count number of a's and c's which ...
user avatar
  • 47
0 votes
0 answers
20 views

Tips on making a grammar LL(1)?

So I currently am given the following grammar, and I have to make it LL(1). To do this, I need to remove ambiguities, eliminate left recursion, and left factor if necessary. But looking at this, it's ...
user avatar
0 votes
1 answer
22 views

What is the subset of CFGs called where each expansion must be the same?

I was wondering about a kind of grammar where we can expand rules of the form A -> X|Y|... with A being a nonterminal and <...
user avatar
  • 103
0 votes
1 answer
29 views

LALR lookahead is wrong, why?

I am studying LALR(1) parser and I have this question: Consider the following Grammar S - > V = E E - > F | E+F F - > V | int | (E) V - > id Construct the LALR(1) parsing table for this ...
user avatar
1 vote
2 answers
51 views

PDA with multiple element access - $i$ - access PDA

We define an $i$ - access PDA as a PDA that can manipulate the top $i$ characters in the stack, where $i>0$. Given a transition function of the form $\delta(p,x,c,d) \to (q,c')$, where $d \le i, d &...
user avatar
  • 15
0 votes
1 answer
27 views

Variant of Chomsky Normal Form for Languages with Strings of Length $\ge 2$

Given a context-free grammar $G$ for a language $L$, where $L$ contains strings of length greater than 2, show that there exists some context-free grammar $G'$ which generates $L$ such that every rule ...
user avatar
  • 15
0 votes
0 answers
76 views

How to convert PDA to CFG and make a state diagram

I'm trying to understand this but I can't figure out how to proceed, I have an initial procedure but I don't know if it's right, could someone give me examples of how to do this? My attempt S→q0 Z q2 →...
user avatar
1 vote
1 answer
101 views

Stuck with shift-reduce conflicts on yacc on grammar to generate palindromic strings on {0,1}

I have written a yacc program for generating palindromic strings consisting of 0s and 1s. Here is the rules section of the yacc program below: ...
user avatar
1 vote
1 answer
132 views

Hierarchy of parser grammars vs Chomsky hierarchy of grammars and the comparsion of the language acceptance power of each parser grammar

While reading the text Modern Compiler Implementation in C by Andrew Appel I came across the hierarchy of grammar given below. The above diagram is very helpful in understanding the correlation among ...
user avatar

1
2 3 4 5
24