Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
908
questions
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$
$\...
