The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
2
votes
1answer
21 views

If you have a smallest grammar approximation, do you immediately have a CFG inference algorithm?

The smallest grammar problem is to find a single-string CFG. So given a finite list of language samples, known to all lie in some CFG, can we, using the smallest grammars (approximated) of each ...
-1
votes
2answers
464 views

How to construct Context Free Grammar of words with equal number of 0's and 1's [duplicate]

i am trying to find a cfg for this cfl L = $\{ w \mid w \text{ has an equal number of 0's and 1's} \}$ is there a way to count the number of 0's or 1's in the string?
1
vote
2answers
108 views

Buchi automata in formal software verification

As I am studying the application of Buchi automata in formal software verification, I am interested in the computational complexity (or links to papers) for the algorithms used to solve the problem in ...
1
vote
2answers
175 views

Is every subset of a RE language also RE, in general?

I'm trying to understand the question in my title in an intuitive way: If I have an RE language A, then some TM, say TM(A) accepts on it. If I take a subset of A, say A2, then all elements of A2 will ...
2
votes
2answers
412 views

Can a Formal Language be of a type (RE, REC, Regular, etc) for one TM, but of a different type for another?

I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this ...
1
vote
1answer
29 views

Set Difference of Two RE Languages - An Intuitive Idea of Why It's Not Closed

I'm new to studying formal languages, so apologies if I get a lot of basic stuff wrong, but I'm trying to get an intuitive understanding of why the difference between two Recursively Enumerable ...
0
votes
0answers
33 views

What is abstract machine for parallel multiple context free grammar (PMCFG)?

It is said, that PMCFG (Parallel multiple context free grammar) http://www.aclweb.org/anthology/P93-1018 is mildly context-sensitive grammar. My question is - what abstract machine can be used for ...
1
vote
1answer
49 views

Is the following Grammar LL(1)

I was given the following grammar $S \rightarrow S ( S ) S\mid \epsilon$ First I was asked to eliminate left recursion, yielding me the following : $S \rightarrow S' $ $S' \rightarrow (S)...
0
votes
0answers
21 views

Are there any formal grammars describing the set of all directed graphs?

Let GRAPHS be the set of all directed graphs. Is there a set of strings STRYNGS such that there exists a bijection ...
1
vote
1answer
181 views

Why can't a left-recursive, non-deterministic, or ambiguous grammar be LL(1)? [closed]

I've learned from several sources that an LL(1) grammar is: unambiguous, not left-recursive, and, deterministic (left-factorized). What I can't fully understand is why the above is true for any LL(1)...
0
votes
0answers
32 views

How a regular language , context free language and context sensitive grammar are used in compilers to shape up the languge? [duplicate]

I know that regular language can be used for pattern matching , context free language is used for syntax matching and context sensitive for semantic or meaning of the sentence . But i have found it ...
1
vote
0answers
51 views

Why full Chomsky hierarchy is so detailed, if there are decidable recursive languages?

One can have a look on the Chomsky hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy , especially the inset named "Automata theory: formal languages and formal grammars" at the bottom of the ...
1
vote
1answer
215 views

Can Deterministic Context free Grammars be ambiguous?

I know that DCFL are unambiguous languages and DCFL languages have one-to-one correspondence with LR grammars. But I wanted to know if there can be an instance that deterministic context free grammar ...
0
votes
0answers
20 views

How to prove that models of indirect and direct RAM machines are equivalent?

as in the title, I am looking for a formal proof how to show that models of indirect and direct RAM (random-access) machines are equivalent. I would really appreciate your help.
0
votes
1answer
25 views

How to solve the following left recursion?

A common left recursion: A -> Aa | B can be solve by transforming it into: A -> BA' A' -> aA' | E However, I ...
1
vote
0answers
22 views

Is there any difference in the expressiveness of boolean grammars versus definite clause grammars?

Definite clause grammars have been around a long time and are included in logic languages such as Prolog. They can be translated into (are just syntactic sugar for) Prolog programs and are therefore ...
0
votes
0answers
22 views

How to find follow sets in this question?

E -> TE’ E’ -> +T E’|Є T -> F T’ T’ -> *F T’ | Є F -> (E) | id How to compute Follow(E),Follow(T),Follow(T’),Follow(E') and Follow(F)?
1
vote
1answer
29 views

Efficiency/Redundancy in Chomsky normal form

I have a context-free grammar with the following production rules, $S$ being the start symbol: $$\begin{align*} S &\to AB \\ A &\to a \\ B &\to a\end{align*}$$ Is this in Chomsky normal ...
0
votes
2answers
126 views

Context free grammar for $\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \}$

Give a context-free grammar for the following language: $\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \}$ So far, this is the solution that I have been able to come up with, though I am not sure how accurate ...
0
votes
1answer
291 views

Prove complement a^nb^nc^n is contextfree

So the complement of L1 = {$a^{n}b^{n}c^{n}$ | n $\geq$ 1} would be L2 = {a,b,c}* \ {$a^{n}b^{n}c^{n}$ | n $\geq$ 1}. In other words, any combinations of a,b and c where we dont have an equal number ...
0
votes
0answers
44 views

contextfree? {w1w2 | w1,w2 $\in$ {a,b}* $\land$ |w1| = |w2| $\land$ w1 $\neq$ w2} [duplicate]

Is this language contextfree? {w1w2 | w1,w2 $\in$ {a,b}* $\land$ |w1| = |w2| $\land$ w1 $\neq$ w2}. I think it's not but can't prove it.
0
votes
0answers
63 views

Context free grammar problem with hashtag

I am trying to solve the following context free grammar problem with hashtag approach but i can't figure it out. Can anyone help please? Show a context-free grammar for the following languages: $$\{w\...
0
votes
1answer
39 views

First Sets: If $A \to Ad\ |\ c$, what is $First(A)$?

Suppose that we have a grammar with the following rules: $$S \to Aa\ |\ b\ |\ \varepsilon\\ A \to Ad\ |\ c$$ From looking at it I already know that $First(S) = \{b, \varepsilon, c\}$. My question is:...
0
votes
1answer
20 views

Grammar with same variables

If a grammar has the same variable multiple times, is it the same as adding a $\mid$ between them? For example, is $$\begin{align*}S &\to bB \\ S &\to \varepsilon \\ B &\to cB \\ B &...
0
votes
1answer
42 views

Context free grammar to Chomsky's normal form

\begin{align*} S&\to AACD\\ A&\to aAb\\ C&\to aC\mid a\\ D&\to aDa\mid bdb\mid\varepsilon \end{align*} I think that this grammar is infinite so it is not possible to convert it into ...
0
votes
1answer
70 views

Unrestricted grammar which generates $\{ a^1\#a^2\#a^3\#\dots \#a^k \mid k >0 \}$

I am looking for an unrestricted grammar which generates the following language: $\{ a^1\#a^2\#a^3\# \dots \#a^k \mid k >0 \}$ That is, words like $a\#aa\#aaa\#aaaa\# \dots \# \text{$k$ times '$a$...
5
votes
2answers
120 views

Is there any other computation theory besides the one in automata theory?

I'm a bit confused at a fundamental level. In Computer Science, maybe some of us mostly use discrete mathematics since our computer is digital (like during studying operating system, algorithms, ...
0
votes
1answer
137 views

LR parsers and ambiguous and non deterministic grammars

Dragon book says: An ambiguous grammar can never be LR. And then immediately further it says: For example, consider the dangling-else grammar: $\begin{align} stmt \rightarrow & \textbf{...
1
vote
0answers
17 views

Clear definitions of various terms related to top down parsers and classification of the same

I am trying to clearly define various terms related to top down parser "so that I can relate them and come up with clear classification". Now this efforts might seem unnecessary as the terms I am ...
0
votes
1answer
213 views

Handling epsilon productions in recursive descent parsing

I am working on a recursive descent parser for lambda calculus. In my grammar, after removing left-recursion, I am left with the following two productions: ...
2
votes
1answer
84 views

How to produce a context free grammar for this language?

I've already attempted it but I am finding it difficult to understand if this is correct. give a context free grammar for the following: $$ \{p^{3m+n}q^nr^2p^m\mid m,n\ge 0 \}$$ The answer i've ...
0
votes
1answer
78 views

Is this a correct grammar for untyped lambda calculus?

I am trying to write a recursive-descent parser for untyped lambda calculus. While researching the way of formulating the grammar, I managed to put together something like this: ...
0
votes
1answer
37 views

Closure properties between two languages from different grammars

We know that if we have two languages produced by one regular grammar, then any language produced from the union, intersection, and so on would be regular. What if we have a regular grammar that ...
0
votes
1answer
51 views

Find a grammar for this language

Assume the language: $$L=\left\{w\in\{0,1\}^*\,| \text{ w has odd length and 111 right in the middle}\right\}$$ This is my attempt for constructing a grammar $G$ for this language: $$G: S \...
0
votes
1answer
61 views

Reusing variable in converting grammar to Chomsky Normal Form

I'm not sure if reusing variable is allowed in CNF. For example, I have this grammar not in CNF. So I have to convert it to CNF. ...
1
vote
0answers
23 views

Generalization of formal grammars - production rules with more general functions?

Usually formal grammars have production rules in the format N=tNt where simple concatenation function is used for the expansion of the nonterminal. https://www....
1
vote
1answer
66 views

context free grammar for palindrome: $L_n = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$

Let $L_{n} = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$ Generate a cfg of $L_n$ For n = 1, 2, 3 Informally, x is in $L_n$ means some palindrome of at least length n is a ...
1
vote
2answers
65 views

How to add decimals to formal grammar?

I have a formal language that describes digit production like <digit> ::= 0|1|2|...|9 and I need to intruduce fraction to write decimals like ...
3
votes
0answers
16 views

Base-k representations of polynomials: state of art [closed]

In chapter 4 of Jeffrey Shallit's A Second Course in Automata Theory the following problem is formulated as open: Let $p(n)$ be a polynomial with rational coefficients such that $p(n) \in \mathbb{N}$ ...
0
votes
1answer
89 views

How to eliminate ambiguity of the follwing CFG?

Consider the following CFG: $S\to AED | F \\ A \to Aa | a\\ B \to Bb | b\\ C \to Cc | c\\ D \to Dd | d\\ E \to bEc | bc\\ F \to aFd | BC$ The CFG produces $a^*bbb...ccc...d^*$ (equal number of b,...
0
votes
1answer
186 views

Proof that the grammar is LL(2)

I am given the following grammar: $ S \rightarrow AabAba \\ A \rightarrow a | \epsilon $ and I have to prove it is LL(2). I know what LL(k) means - one can choose a production based on k characters ...
1
vote
2answers
46 views

Why can't exhaustive search parsing stop after |w| + 1 derivations?

If my grammar does not have productions of the form $A\rightarrow\lambda$ and $A\rightarrow B$ for some variables $A$ and $B$ then I know that each step in the derivation must involve an increase in ...
2
votes
1answer
149 views

How to prove prove $L(G) = \{~w\in\{a,b\}^*~|~\#_aw= \#_bw\}$ for my CFG $G$?

For language $L = \{ x \in \{a,b\}^* \mid \#_a x = \#_b x \}$, I came up with the following CFG: $$S \rightarrow aSbS \mid bSaS \mid \varepsilon.$$ It can be easily shown that it is correct (quick ...
0
votes
1answer
50 views

Context-Free Grammar from this language

I'm having difficulties with an exercise in a theoretical CS class. The problem is: let $L_{2}$ be a language defined as follows: after every "a" come atleast two "b" or after every "b" comes atleast ...
-1
votes
1answer
148 views

Convert grammar to Greibach form

The grammar is $S \rightarrow AA|a$$A \rightarrow SA|ab$The actual question is to find an NPDA accepting the language generated by this grammar but for that i firstly need to convert it into Greibach ...
1
vote
1answer
188 views

CFG - Ambiguous to Unambiguous

Given the ambiguous CFG : S → 01S1|SS|ϵ I came up with the following CFG which I think is unambiguous: S → 01X | 011X X → 01X1 | ϵ Is my CFG unambiguous and does it represent the same language?
3
votes
2answers
925 views

CFG for language of all palindromes whose number of 1s is divisible by 3

The question is the following: Construct a CFG for $L_2 = \{w \in \{0, 1\}^* \mid w = w^R\text{ and the number of 1’s in $w$ is divisible by 3}\}$. I can construct a CFG for $\{w \in \{0,1\}^* \...
0
votes
1answer
39 views

What's wrong with this grammar

$L = \{ w : w \in \{a, b\}^* \land |w|_a = |w|_b\}$ where $|w|_a$ means number of $a$ in string $w$. I came up with this grammar: $S \rightarrow aSb \ |\ bSa \ | \ \epsilon .$ Can someone please ...
3
votes
0answers
99 views

Simple description of circularities in Knuth original attribute grammar paper

Knuth's original attribute grammar paper (title: Semantics of Context-Free Languages) introduced three types of circularity. More specifically section "Testing for circularity" page 134-5 figures 3.1-...
3
votes
1answer
146 views

Find a regular grammar that generates words with even number of a's

I have a language $L$ = {$vabu$ | $v$,$u\in \{a,b\}^*$, $|vu|_a = 0$ $($mod $2)$$\}$ where $|vu|_a$ is number of $a$ in $vu$. I came up with these rules: $\sigma \rightarrow aa\sigma | ab\xi$ $\...