2
votes
1answer
59 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 ...
1
vote
1answer
51 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: ...
0
votes
1answer
33 views

Chomsky Normal Form for Integer Recognition

If I have the following CFG, which is just the regex [0-9]+: ...
1
vote
1answer
33 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
59 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
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 ...
1
vote
0answers
75 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
34 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
80 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
57 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
117 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
56 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 ...
1
vote
1answer
99 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
24 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
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, ...
2
votes
0answers
41 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
134 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
283 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 ...