0
votes
0answers
31 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 ...
0
votes
0answers
20 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
74 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
35 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
45 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
23 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
31 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
45 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
128 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
61 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
41 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
115 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
117 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
49 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
141 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
50 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
67 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
1answer
108 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
182 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
96 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
102 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
897 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
355 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
106 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 $}$ ...