0
votes
0answers
9 views

Chomsky Normal Form for Integer Recognition

If I have the following CFG, which is just the regex [0-9]+: ...
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 ...
2
votes
1answer
32 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 ...
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 ...
0
votes
0answers
29 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 ...
0
votes
0answers
22 views

Eliminating Immediate Left Recursion

I understand that in order to eliminate an immediate left recursion from a grammar containing production of the form $A\implies Aα$ I need to replace it by $A\implies βA'$ and $A'\implies αA/∈$ Im ...
1
vote
1answer
70 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
48 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 ...
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 ...
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?
1
vote
0answers
23 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
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, ...
2
votes
0answers
35 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
127 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$), ...
0
votes
1answer
218 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?
1
vote
1answer
2k 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 ...