0
votes
0answers
24 views

Smallest grammar problem on a single character.

Let the alphabet be $\Sigma = \{a\}$. Say $s = a^6 = aaa aaa$. If the repeated variable $A = aa$ appears $k$ times in the expanded starting rule of a smallest grammar $G_s$ for $s$. Then that ...
-1
votes
0answers
18 views

The max number of repeats of substrings of a sample of a language.

So we suspect that finding the smallest grammar of strings in the language $\{a^n : n \in \Bbb{N}\}$, is hard. But luckily as far as applications to natural language processing, we would rarely ...
0
votes
0answers
18 views

Do automatons and formal grammars belong to formal systems

A formal system consists of a formal language, a formal grammar that generates the language, a set of axioms, and a set of inference rules. Are automatons also formal systems? Is an automaton ...
1
vote
1answer
50 views

Context free grammar $L=\{a^ib^jc^k|j=i+k-2\}$

$L=\{a^ib^jc^k|j=i+k-2\}$ This expression surprise me a lot and put me into deep thinking. what i am doing by solving the expressions: ...
1
vote
1answer
32 views

There is a sequence of operations on grammars of a string that strictly decreases the size of grammars down to the smallest grammer.

I'm trying to figure out the smallest grammar problem, which yes I know is impossible since it's such a hard problem, but humor me for a sec. Let $g$ be a smallest grammar for the string $s$ over the ...
0
votes
1answer
34 views

Palindromes with 2 symbols and $3|l(u)$

The following grammar generates palindromes with 2 symbols. $$G=\{\{S\}, \{a,b\}, \{S\rightarrow\epsilon|a|b|aa|bb|aSa|bSb\}, S\}$$ So if I'm right, each $u$ in the language $L$ generated by $G$ is a ...
0
votes
1answer
22 views

How can I show ithat a language is regular?

I have a very quick question about regular languages, I think $\{a^{2n}| n\geq 1\}$ is regular. I do know that pumping lemma can be used to show something that is not regular. I am wondering what ...
0
votes
1answer
27 views

Question About Pumping Lemma used on a FA

I am learning about pumping lemma and I am trying to solve a problem. I need to use pumping lemma to show that: the Language L(M) defined by the following machine is infinite. Here is the dfa: ...
0
votes
1answer
40 views

Creating a Push Down Automaton from a Grammar

I have the following grammar, but I'm not sure what exactly it is that it does: $\qquad\begin{align} S &\to S \vee T \mid T \\ T &\to T \wedge F \mid F \\ F &\to p \mid \thicksim p ...
2
votes
1answer
111 views

Converting Context Free Grammar to Chomsky Normal Form

This is an exercise that I had to complete in my class and I struggled a lot with it $$\begin{align*} &S\to 0A0\mid 1B1\mid BB\\ &A\to C\\ &B\to S\mid A\\ &C\to S\mid\epsilon ...
1
vote
1answer
54 views

Grammar outside the Chomsky Hierarchy

This grammar describes a language that may fall outside the Chomsky Hierarchy (CH): \begin{array}{l} S \to abAbba \\ A \to abA \mid bbaB \\ B \to aab \\ \lambda \to Aab \mid aB \\ \end{array} Going ...
1
vote
1answer
39 views

Consider this grammar

Consider this grammar: \begin{array}{l} S \to aabBba \mid aAb \mid aab \\ bBb \to bCa \mid aaa\\ aA \to aC \mid bba\\ C \to aab \mid Cb \end{array} This is clearly context-sensitive (CS). It's not ...
0
votes
0answers
37 views

Context-sensitive grammar for this language

In order to write a context-sensitive grammar for: $L = \{ a^{n} b^{n} c^{n} d^{n} : n \ge 1 \}$ One possible set of productions is: $S \rightarrow aBCd | abcd $ $aB \rightarrow aaBb | ab | ...
0
votes
1answer
114 views

Help with context sensitive grammar [closed]

I am not able to understand writing a context sensitive grammar for this language. Can anyone please help me out? $L = \{ a^p | p \text{ is a non-prime integer}\}$
1
vote
1answer
95 views

Write a grammar that generates the strings over {a,b} starting with a

The answer is: S -> aA, A -> aA, A -> bA, A -> a, A -> b, S -> a Any idea how they got this?
2
votes
1answer
45 views

NFA from grammar productions

Based on this grammar: \begin{align} G = (\{S,A,B\}, \{a,b, c\}, S, P) \end{align} \begin{matrix} \\P: \\S → abaS | cA \\A → bA | cB | aa \\B → bB | cA | bb \end{matrix} I created this NFA: ...
0
votes
1answer
106 views

Right-linear grammar from regular expression

I made a right-linear grammar that from this regular expression: The alphabet is: $Σ = \{a, b, c\} $ Regular expression: $r = cc^*(ba)^*bb$ My solution, it seems a little too short like I'm ...
1
vote
1answer
48 views

NFA from regular expression

I'm trying to make an NFA from the following regular expression. I'm not sure about the edges between nodes $q2$ and $q4$, maybe someone can point out where everything went wrong.
0
votes
1answer
27 views

Language made by a regular expression

I created a language from this regular expression but I'm not sure about it, especially where I wanted to use the $w$ to express a sequence of terminals. The expression: $r = a a ^{*} (b + bb + bbb) ...
1
vote
1answer
23 views

Regular expression for a language

I made a regular expression to match this language but I'm not sure it's right. Perhaps someone can show me where it deviates. The language: $L = {a^{n} c b^{m} (cc)^{p} : n \geq 1, m \leq 1, p\geq ...
0
votes
2answers
66 views

Constructing regular grammar

I'm trying to make a regular grammar for this language: $$ L = \{ a^ncb^m(cc)^p : n\ge 1, m\le 1, p\ge 0\} $$ Where the alphabet is $ \Sigma = \{a,b,c\}$ It seemed like right-linear. This may be ...
0
votes
0answers
30 views

How to verify Formal Language Grammar?

In Theory of Computation I am taking the introductory sections of: Languages and Grammar In the homework given, I am asked to provide Grammar for multiple languages. I did number of possible grammar ...
0
votes
1answer
103 views

Understanding how to convert a PDA to a CFG

Given a PDA, initialized with $\#$ on the stack, and with accepting states $q_a, q_b, q_c$ and the following transitions: (current state, stack head, input character, replacement for old stack head, ...
0
votes
1answer
171 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
75 views

Are there any trivial examples of languages that cannot be produced by formal grammars?

Since the cardinality of the set 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 ...
0
votes
1answer
14 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$ ?
0
votes
2answers
62 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 ...
1
vote
1answer
93 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
101 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 ...
6
votes
2answers
865 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
334 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
104 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
69 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 $}$ ...