Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
1
vote
1answer
14 views
Converting CFG from GNF to CNF
I am working with grammars that need to be in Greibach Normal Form. I want to check whether a grammar recognises a string. In order to perform CYK the grammar would have to be converted into CNF. Is ...
-1
votes
1answer
44 views
How construct PDA to $L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$
$L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$
I don't have any idea. Can someone help me.
0
votes
1answer
41 views
Is complement $L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ context-free
$L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$
In my opinion complement of the L language is
$L^{C} = \{ w : |w|_{a} \neq |w|_{b} \wedge |w|_{c} \neq |w|_{d} \}$
I choose to ...
1
vote
2answers
68 views
Is the language of words that contain a square regular or context-free? [duplicate]
$ L = \{w \in\{a,b\}^{*} : \exists_{x,y,z} , w=xyyz \wedge y \neq \epsilon \}$
I have a problem with this exercise. I need to determine if this language is regular, context-free or not both and ...
3
votes
2answers
81 views
How to prove the equivalence of two CFG for balanced parentheses?
Given two CFGs for balanced parentheses.
$S \rightarrow SS \mid (S) \mid \epsilon$
$S \rightarrow S(S)S \mid \epsilon$
How do I show that they are equivalent?
I have been able to show $ L(2) \...
1
vote
1answer
26 views
Prefix/suffix property of language containing only empty word
Does language $L ={\varepsilon}$, where $\varepsilon$ - empty word has suffix/prefix property?
The definition says that language has prefix/suffix property requires that there is no code word in the ...
4
votes
1answer
53 views
Is there a recommended process for designing CSGs (other than intuition)?
I understand the differences between Regular, Context-Free, and Context-Sensitive languages. Designing a Regular Grammar can be easier if you have a DFA. Designing a CFG isn't too hard for the ...
0
votes
0answers
13 views
Difference between grammar productions and derivations
My understanding is that a production is a 'rule' of a grammar which defines how a symbol sequence can be rewritten into another symbol sequence.
A derivation on the other hand is the process of ...
-2
votes
1answer
42 views
Provide “regular” grammar for this language {${a^ib^j \mid i>0\ and \hspace{2.5mm}i\leq j \leq(2*i)}$} [duplicate]
I'm trying to understand the approach to constructing an grammar which accepts the language
${a^ib^j \mid i>0\ and \hspace{2.5mm}i\leq j \leq(2*i)}$ }
Thanks.
0
votes
0answers
19 views
What is “Phrase structure grammar”?
I'm undertaking Theory of Computation Classes. I came across this sentence while studying Recursively Enumerable Grammar:
Type-0 grammars generate recursively enumerable languages. The
...
0
votes
1answer
29 views
Does left factoring CFG make it unambiguous?
I came across following problem:
If the CFG is left factored then it must be Unambiguous and Not left Recursive.
TRUE/FALSE?
I have many thoughts about this. But I feel they are somewhat ...
0
votes
1answer
38 views
Chomsky Classification of Languages
Given is a language $A = \{ a^n\:b\:c^{2n}\:b^m |\; n ∈ N^{+} ;\; m ∈ N \}$ ; where $N^{+}$ are the natural numbers excluding 0.
I have found a type-1 grammar to describe it:
$S \to A_1A_2$
$A_1 \...
1
vote
1answer
35 views
Is this context-free grammar correct for this regular expression?
I have created a context-free grammar
$$
\begin{align*}
&S \to S_1 \mid S_2 \\
&S_1 \to aS_3bS_4 \mid \epsilon \\
&S_2 \to bS_4 \\
&S_3 \to aS_3 \mid \epsilon \\
&S_4 \to aS_4 \...
1
vote
3answers
74 views
Give a grammar for words whose number of $a$'s modulo 2 is larger than whose number of $b$'s modulo 2
Given is an alphabet $\Sigma = \{ a, b, c \}$, and a language $A4 =\{ w \mid w \in \Sigma^* \wedge |w|_a \operatorname{mod} 2 \ge |w|_b \operatorname{mod} 2 \}$
whereas $|w|_a$ is the number $a$'s in ...
0
votes
1answer
22 views
How to generate a grammer from this language? [duplicate]
I'm trying to generate a grammar from this language:
L={a^i b^j c^k d^l : i+j=k+l}
to be clear its a in the power of i and b in the power of j... and so on, so ...
1
vote
1answer
28 views
Is there any relationship between grammar being ambiguous and the language itself?
According to my understanding, a grammar is ambiguous if it generate strings which can be interpreted in more than one ways ( that is , more than one parse tree), but when it comes to the language ...
0
votes
1answer
52 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
2answers
39 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
16 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
39 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
63 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
52 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
382 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
25 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
34 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
20 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
35 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
21 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
29 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
102 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
16 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
20 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
20 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
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
114 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
62 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
18 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
29 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
38 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
30 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
38 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
99 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
44 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
56 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
77 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:
...
