The formal-grammar tag has no wiki summary.
0
votes
1answer
59 views
Formal grammar for the language $L = \{w\in\{a,b\}^*,\,w=xx,\,x=a^nb^na^mb^m,\,n\ge0,\,m\ge0\}$
What is the grammar of this language?
$$L = \{w\in\{a,b\}^*,\,w=xx,\,x=a^nb^na^mb^m,\,n\ge0,\,m\ge0\}$$
For example: $abab$, $abaabbabaabb$
3
votes
2answers
44 views
Are there any trivial examples of languages that cannot be produced by formal grammars?
Since the cardinality of all languages that can be produced by a grammar is smaller (countably infinite) than the cardinality of the set of all languages (which is uncountable infinite) I'm wondering ...
0
votes
1answer
12 views
What is the name of a variable $v\in V$ in a grammar $G=(V,T,P,S)$ s.t $v\Longrightarrow_{G}^{*}\epsilon$?
I have a variable $v\in V$ in a grammar $G=(V,T,P,S)$ s.t $$v\Longrightarrow_{G}^{*}\epsilon$$
Where $\epsilon$ is the empty string.
Is there a name for such a variable $v$ ?
2
votes
0answers
21 views
defining relationship between geometric entities (features)
I have different features located on a plane (2D); I want to define this structure mathematically in a way to represent their relations. Some of features are aligned in horizontally, vertically or ...
0
votes
1answer
68 views
Finding context-sensitive grammar for a given language
I was wondering, in my other topic, how to find grammar for: $\left\{ a^n b^n c^n: n\ge 1 \right\}$ when I found this. Context-sensitive grammars is completely new topic for me and I don't understand ...
0
votes
1answer
28 views
Expression Writing: Random variable inside bayesian (Notation)
What is the best, most clear way to denote this example.
Event A: outcomes (0,1).
P(C)=P(B), if A=1
P(C) = 0, if A=0
Which one is best
1) P(C) = P(B|A=1), A: indicator random variable
2) P(C) ...
1
vote
0answers
29 views
Enumeration of symbols in grammatical expressions or vertices in tree graphs
I have expressions (type of a function) like e.g.
$$f:(A\to B)\to C \to (D\to E)\to F.$$
(Where I understand $A\to B\to C$ as $A\to (B\to C)$, in case that is relevant.)
There might be information ...
0
votes
1answer
100 views
Regular grammar and context grammar problems
If $G$ is not a regular grammar, then $L(G)$ is infinte.
If $L^*$ is context free then $L$ is definitely context free.
If $G$ is a context free grammar that is language is $L$ (meaning $L(G) = L$),
...
2
votes
1answer
47 views
Is regularity is preserved under reversal?
When talking about languages and regular languages.
Can I say that reversal preserved regularity since if the language L is regular, we can generate it by right linear grammar.
Therefore, the ...
0
votes
3answers
73 views
The set of words in {a,b,c}∗ that do not contain the substring bc.
I couldn't write nfa or dfa for the language above. Please, help me!
1
vote
2answers
58 views
Solve right linear set equations
Trying to solve this set of equations. I'm feeling like I'm making it so complicated.
Of course + is union. Am I on the right track?
A = 0B + 1D
B = 0C + 1A
C = 0A + 1B + λ
D = OD + 1C + λ
A ...
0
votes
0answers
51 views
Grammar with a single left derivation but multiple right derivations
Now I'm reading about formal grammars (namely, context-free ones) and the author defines an unambigous grammar as a grammar where each derivable word has only one left derivation, but he says nothing ...
0
votes
1answer
93 views
Prove that L(G1) is a regular language
G is a context free grammar which all productions are of the form
$X \to aY$
or
$X \to a$
Where X, Y are nonterminal and a is nonempty terminal string.
How can I prove it is a type 3 grammar?
0
votes
2answers
49 views
Confusion related to the type 3 grammar
I have this confusion. Lets say I have language produced by type 3 grammar such that
L(G1) = <Vn1,Vt,P1,S1>
I need to find a type3 grammar G3 such that
...
0
votes
2answers
64 views
Confusion related to a context sensitive grammar
I want to know if I have the following rule
$$AB \to BA$$.
Is it context sensitive?
Another rule
$$A \to aAB$$
Is it context sensitive as well.
I think both of them are not context sensitive. ...
2
votes
1answer
71 views
Confusion related to context sensitive grammar
I have this confusion related to context sensitive grammar. I was referring to this article http://en.wikipedia.org/wiki/Context-sensitive_grammar. And it has given an example of production rules for ...
0
votes
1answer
28 views
Estimate size of L-system string
I am writing a program to work with L-systems (Lindenmayer Systems) and I need to know how much memory to allocate for the strings, but my problem is clearly a math problem, not a programming one. ...
5
votes
2answers
452 views
Context-sensitive grammar for the copy language
I need to find a context-sensitive grammar for the copy language
$$L = \{ww \; | w \in \{0,1\}^* \}$$
This is what I got so far:
$\begin{eqnarray}
S & \Rightarrow & \lambda \; | \; X \\
X ...
2
votes
1answer
168 views
“Best practice” for finding the language of a formal grammar
If I've been given a formal grammar like
$$
\begin{eqnarray}
S & \Rightarrow & \lambda & | & 0A & | & 1B \\
A & \Rightarrow & 1S & | & 0AA \\
B & ...
1
vote
2answers
81 views
Finding a grammar for a formal language
I am looking for a grammar that describes the formal language
$L = \{ xyx^R \;|\; x,y \in \{a,b\}^*\}$
where $\{a,b\}^*$ corresponds to the regular expression [ab]*.
If there would be no y and the ...
1
vote
1answer
854 views
Why is this Parsing Expression Grammar left recursive?
I'm trying to get my parser generator to accept this specification. I know that's kind of a programming question, but I figured this was the best place to ask. It's specified as a Parsing Expression ...
1
vote
1answer
61 views
Prove that L($G^R$) = $(L(G))^R$
I'm stuck with this exercise from a course in formal languages that I am taking.
Could someone help me with this?
Big thanks!
For any w, define $w^R$ as
$\lambda ^R \text{ = $\lambda $}$
...
