The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
12 views

Relaxation of the null production restriction in Regular and Context Free Grammars [migrated]

I am convinced of the fact that allowing productions of the form $S \rightarrow \epsilon$ in a context sensitive grammar would allow RE languages to be expressed if $S$ were on the right hand side of ...
0
votes
0answers
18 views

Construct a grammar that generates this language

This is a homework problem. The problem is: Find a grammar that generates this language: L = {w: |w| mod 3 ≠ |w| mod 2} over alphabet Σ = {a}. The transitions I came up with are: S -> Baa B -> ...
1
vote
2answers
32 views

Find a grammar that generates this palindrome language

This is a homework problem. The problem is: Find a grammar that generates this language: L = {wcw^R: w ∈ {a,b}+ } over alphabet Σ = {a, b, c}. I have tried many different transitions, but can't ...
-1
votes
0answers
28 views

Model Computation

My question is to give a phrase-structure grammar that generates the set $\{0^n1^n \mid n = 0, 1, 2, \dots\}$. I am familiar with the concept of language generations but I couldn't get the main idea ...
0
votes
1answer
48 views

Determine type of grammar?

Let $V = \{S, A,B, a, b\}$ and $T = \{a,b\}$. Determine whether $G = (V, T, S, P)$ is a type $0$ grammar but not a type $1$ grammar, a type $1$ grammar but not a type $2$ grammar, or a type $2$ ...
0
votes
1answer
22 views

Given the following grammars with start symbol $\langle S \rangle$, specify the type ($0$, $1$, $2$ or $3$)

So I'm working on this problem set and I'm having some trouble figuring out what type each one of these are. I think (a) is type $0$ and really can't tell for (b). I know the difference between each ...
0
votes
1answer
96 views

Turing Machine Problem

We know, A Turing machine is a hypothetical device that manipulates symbols on a strip of tape according to a table of rules I Draw a TM for input $x=(0+1)^*$ i want to implement ...
0
votes
0answers
35 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
vote
1answer
53 views

Regular Language and Unknown Operation

I read the $L$ is a Regular language. Define $L'$ as following: $$L'=\{a_2a_1a_4a_3\ldots a_{2n}a_{2n-1}\mid a_1a_2\ldots a_{2n} \in L\}.$$ why $L'$ is Regular? any hint or idea would be highly ...
0
votes
0answers
27 views

Algebra on trees?

Given a forest of trees, I am interested in tree recombination operations that produce me a sub-forest spanned by some selected trees. To me, it somehow resembles space and spanned subspace in ...
0
votes
0answers
27 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 ...
0
votes
1answer
33 views

Predictability of a grammar

I've encountered this in a book: The language $ \{ a^n0b^n \mid n ≥ 1\} ∪ \{a^n1b^{2n} \mid n ≥ 1\}$has no predictive grammar. (A predictable grammar is that in which no two rules of production for ...
1
vote
1answer
104 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
0answers
32 views

What about generlizing grammars?

Say we came up with a finite grammar (specifies a finite number of strings) given a set of input strings. How then do we generalize the grammar so that it works for larger input strings and also ...
0
votes
1answer
36 views

Chomsky Normal Form for Integer Recognition

If I have the following CFG, which is just the regex [0-9]+: ...
1
vote
1answer
38 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 ...
3
votes
1answer
76 views

Why use *λx.x* instead of *f(x)*?

In my semantics class, we're learning about using (abusing?) lambda calculus. So far the professor hasn't imparted any reason for using λx.x instead of using f(x). Why use lambdas instead of basic ...
2
votes
1answer
108 views

Is well formed XML context-sensitive grammar?

Solution Copy language is noncontracting, so it's context-sensitive. Look at https://en.wikipedia.org/wiki/Noncontracting_grammar for transforming noncontracting grammar to explicitly $\alpha ...
4
votes
3answers
348 views

How to denote this in game theoretic notation

I'm writing a paper that demonstrates that linguists can use the concepts in game theory to infer what interlocutors naturally infer when the literal meaning of their utterances doesn't ostensibly ...
0
votes
1answer
56 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
26 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
37 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
34 views

How to notate truth conditional functions

My semantics professor uses functions to teach her class. She wrote the following sentence and three examples in one of her slides. [[smile]] is a function that takes something, let’s call it x, and ...
0
votes
1answer
57 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
198 views

Eliminating Epsilon Production for Left Recursion Elimination

Im following the algorithm for left recursion elimination from a grammar.It says remove the epsilon production if there is any I have the following grammer ...
1
vote
1answer
90 views

Context free grammar for a language

I have this context free language $L = \{x^{3i} y^j z^k\ |\ i \ge 0 \land k \gt 2j \gt 0\}$ I'm working out a ...
0
votes
1answer
64 views

Shortest word possible

In a give context-free grammar language $L = \{z^{3x} y^i w^j \ |\ x \ge 0 \land j \gt 2i \gt 0\}$ The shortest possible word that does not belong to the ...
2
votes
1answer
186 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
76 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
44 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
42 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
119 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
174 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?
0
votes
1answer
855 views

Build regular grammar from regular expression

Is there an algorithm for creating a regular grammar directly from a regular expression? All the discussions and notes I found so far go through an intermediary step of creating an FA for the reg ex ...
2
votes
1answer
57 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
178 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
53 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
30 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
25 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
71 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 ...
1
vote
0answers
25 views

What do you call a mildly-context sensitive grammar in which the LHS must appear in the grammar spec?

For instance: $$ S \rightarrow aAbAb \\ aAb \rightarrow AAa \\ A \rightarrow Aa | a $$ $aAb$ is alright to have on the left-hand side since it occurs directly in the grammar spec. Further indirectly ...
0
votes
1answer
130 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
196 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
82 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
15 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
42 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
355 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
52 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
48 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
138 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$), ...