Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
0
votes
1answer
46 views
Ambiguous grammar to equivalent unambiguous grammar
I stumbled on this ambiguous grammar and I've been trying to make it unambiguous but it's still ambiguous.
Given the ambiguous CFG :
$S \to A\mid B$
$A \to aAb\mid ab$
$B \to abB\mid \epsilon$
My ...
1
vote
0answers
35 views
A look at an exact smallest grammar algorithm. How do we compute running time big-O?
A smallest grammar of a string $s$ over an alphabet $\Sigma$ is a smallest CFG $G$ such that $L(G) = \{s\}$, where size is the total number of symbols occuring on the right sides of production rules ...
1
vote
2answers
36 views
What's the right way to think about a CFG symbol with an infinite null derivation?
I'm curious about the right way to characterize symbol $A$ in a CFG like this one:
$$
\begin{align*}
A &\to A B\\
A &\to x\\
B &\to y\\
B &\to \varepsilon
\end{align*}
$$
$B$ is ...
1
vote
1answer
14 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
30 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
53 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
49 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
374 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
19 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
18 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
33 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
19 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 ...
0
votes
1answer
28 views
Why can't a left-recursive, non-deterministic, or ambiguous grammar be LL(1)?
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
20 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
26 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
84 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
15 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
19 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
15 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
19 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)?
0
votes
0answers
35 views
Find grammar for x^i/y^j/z^k where i>=j>=k
It is context free language, but i don't know how to solve the condition of the language... thanks for hint
1
vote
1answer
14 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
109 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
46 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
13 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
27 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
35 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
19 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
27 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
36 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$...
-1
votes
0answers
26 views
Context-free grammar for the language $L_a=\{w:w \neq uu, u\in L((a + b)^*)\}$ [duplicate]
To my understanding, $(a + b)^*$ is a regular expression equivalent to the language $\{a, b\}^*$. Thus, $L_a=\{w: w \neq uu, u\in L(\{a, b\}^*)\}$.
I'm trying to simplify the language even further so ...
-1
votes
0answers
13 views
Is there a Context-free grammar for a^(n^2) [duplicate]
The language was L1 = {a^(n^2) : n>=0}. I knew a^(n^2) can also be expressed as a^(nn). I ...
5
votes
2answers
97 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
34 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
15 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
50 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
75 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
41 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
28 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
27 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
29 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
votes
0answers
18 views
Merging nonterminals of a Context-Free Grammar?
I am reading through a paper on grammatical inference and stumbled upon the following:
Given positive example w, we first construct the tabular
representation T(w) and the primitive CFG G(T(w)), ...
1
vote
0answers
18 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
41 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
43 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
14 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
40 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
61 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
1answer
14 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
103 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 ...
