1
vote
1answer
23 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
28 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
20 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
22 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
27 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 ...
1
vote
1answer
45 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
35 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
31 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
107 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
45 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
42 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
93 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
42 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
24 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
21 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
58 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
27 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
88 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
154 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
72 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
13 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
60 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
84 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
93 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
735 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
305 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
96 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
68 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 $}$ ...