Questions about formal grammars, generative descriptions of formal languages.

learn more… | top users | synonyms (1)

1
vote
0answers
23 views

Quick testing tool for context sensitive grammars

Is there a ready-made tool / library that takes as input a context sensitive grammar $G$ over an alphabet $\Sigma$, and gives the ability to quickly check if a set of strings $\{w_1, w_2, ..., w_n \}$ ...
0
votes
2answers
62 views

Finding Language of a CFG

Say you are given the following CFG $G$: $$ S \to S_1 \mid S_2 \\ S_1 \to AbAS_1c \mid \epsilon \\ S_2 \to BaBS_2c \mid \epsilon \\ A \to Aa \mid \epsilon \\ B \to Bb \mid \epsilon $$ What is $L(G)$? ...
0
votes
0answers
29 views

How to see if P is decidable semi-decidable, undecidable?

I've been trying to figure out a practice exam question, about if a given $P$. $P$ is the characteristics of recursive enumerable set given as: $$P(A) = \begin{cases} ⊤ &if &|A| ≤ 100 \\ ...
3
votes
1answer
44 views

Is $\{a^nb^n\}\cup\{a^nb^{2n}\}$ LR(k)?

I was reading Knuth's paper "On The Translation of Languages from Left to Right", my particular interest being on RL($k$) languages (not a typo). By the end of the paper, he puts the grammar: $$ S \...
-5
votes
0answers
25 views

Grammar for concrete syntax [closed]

It is given concrete syntax: data Stmt = SExp Exp | String := Exp | SBlock [Stmt] ...
-1
votes
0answers
23 views

Intersection of two lanauages [on hold]

I'm preparing for my exam solving exercises from old exams. I'm not sure if my solutions are correct. Could you check following examples? 1) There is given $G_1=\{S_1 \rightarrow abS_1b,\ S_2 \...
3
votes
1answer
54 views

How do you call alternatives in the grammatical productions?

I have encountered a question, which asks what is a syntactic form. This motivated me to ask myself, what is the anatomy of the grammatic rule, ...
3
votes
0answers
30 views

Is asking a LL(1) parsing table for this grammar a trap?

I'm trying to solve some exercises for the upcoming Compilers' exam. Teacher gave us some sheets from previous exams to practice with - no answers provided. Let $\mathcal{G}$ be the following ...
-3
votes
0answers
32 views

Epsilon productions in CLR(1) and LALR(1) parsers

I have read that epsilon productions are treated as final elements. Take for example the grammar: A → AB | ε B → Bc | d in state 0 we would have: ...
1
vote
1answer
27 views

What is the cardinality of the set of regular grammars?

What is the cardinality of the set of regular grammars? The caveat is that I'm only interested in grammars which are 'structurally' different. Sorry I don't know how to talk about this in a formal ...
3
votes
0answers
19 views

How to refactor a grammar to be suitable for recursive descent?

I'm trying to learn how to use a recursive descent parser, and reading on this page I find this example: $S \rightarrow AB \\ A \rightarrow a \\ A \rightarrow SA \\ B \rightarrow b \\ B \rightarrow ...
-3
votes
1answer
42 views

What's the step for build a SLR table for the following CFG? [closed]

(r1) E → E+T (r2) E → T (r3) T → T F (r4)T →F (r5) F → F∗ (r6) F → a (r7) F → b I am just doing the exercise on the workshop. I just knew how to the build the SLR state machine for this CFG. ...
1
vote
1answer
34 views

operator precendence grammar

According to this post http://stackoverflow.com/questions/28397767/computing-leading-and-trailing-sets-for-context-free-grammar while constructing operator precendence parser we have to create tabel ...
7
votes
2answers
89 views

Why is BNF considered an unsatisfactory technique for describing a language?

I was reading the paper Fundamental Concepts in Programming Languages by C. Strachey the other day, wherein I read something that was quite strange to me. Quoting directly (with the strange part ...
0
votes
0answers
27 views

Lossless Condensing, Modification, and Decondensing

Given a string $\alpha$ that is derived from context-free grammar $G$, what is an algorithm $f$ such that there exists a string $\beta$ (derived from an unrestricted grammar) where $f(\alpha)=\beta$,...
3
votes
1answer
48 views

Is the word problem of CFLs in NC?

Consider the membership problem for a context-free language. An instance of this problem can be described as pair $(G,w)$, where $G$ is a context-free grammar and $w$ is a string. Lets say I have a ...
0
votes
1answer
39 views

The Chomsky–Schützenberger representation theorem

I've been trying to proof The Chomsky–Schützenberger, but I stuck on creating regular language from that theorem. I mean reagular language, which is intersected with Duck language. Could anyone give ...
3
votes
1answer
38 views

How to recursively infer a word/string from a context-free grammar?

Give the recursive inference of the word $abcddd$ from the Context-free Grammar: $A\rightarrow aAd\mid B$ $B\rightarrow bBd\mid C$ $C\rightarrow cC\mid cD$ $D\rightarrow Dd\mid ϵ$ This is ...
4
votes
1answer
55 views

How to use Parikh's Theorem to show language is not context free

Parikh's Theorem is quite complicated, I understand intuition of that theorem but I don't see how to use that to prove that language is not context free. I kindly ask you to show me how to do, ...
0
votes
0answers
25 views

what is ( simple grammar ) in automata language? [duplicate]

what is ( simple grammar ) in automate language ? please tell me clearly . i don't understand after twice reading ... what is different between this and regular grammars ? What relation exists ...
13
votes
1answer
328 views

Is language equality for linear context-free grammars decidable?

Let's consider two context-free grammars $G_1$ and $G_2$ and ask the following question: Is $L(G_1) = L(G_2)$, that is, are the two grammars equivalent? In general, this problem is undecidable. ...
4
votes
2answers
490 views

Does a context-free grammar with multiple variables have a “starting” point?

So lets consider the following grammar $$ \begin{align*} S &\to 0 \mid 0A \\ A &\to 1 \end{align*} $$ would the string "1" be accepted by the language or must the language start with $S$?
1
vote
1answer
77 views

Can every context free grammar be transformed into equivalent grammar of this form?

Show, that every context free grammar can be transformed into equivalent context free grammar ( with possible loss of $\lambda $ ) where $a \in V_t$ and $A,B,C \in V_n $ with rewriting rules of ...
3
votes
1answer
23 views

Can an (extended) regular grammar have multiple nonterminals in its RHS?

Standard (right) regular grammars have three kinds of rules: A <- "" A <- "a" A <- "a" B This is OK for a theoretical point of view, but a big ...
0
votes
1answer
25 views

Right linear grammar special case

According to the definition, the productions of a right linear grammar should have the form of $A\to xB$ or $A\to x$, does $A\to B$ or $A\to xy$ count as productions of a right linear grammar? $A\to B$...
0
votes
1answer
45 views

Showing a language is context free. Use PDA or CFG?

I am wondering on how to approach a specific problem I am struggling with. I am not understanding which way to approach it and how to solve it. Show language $L$ is context free, where $L = \{\text{...
0
votes
1answer
28 views

Why descriptive power of context-free grammar is greater than regular expression?

Below is a saying from this article. Regular expressions sit just beneath context-free grammars in descriptive power: you could rewrite any regular expression into a grammar that represents the ...
0
votes
1answer
24 views

How can I show context free grammars are strictly more expressive than regular expressions with an example?

I need to show a CFG can express everything that can be expressed by a regular expression, and something that cannot.. I have no idea what example is traditionally used for this.
7
votes
1answer
461 views

Is it possible to build DFA for odd-length words with 1 in the middle?

$L := \{w \in \{0,1\}^* | $the length of $w$ is odd $ \wedge $ 1 is in the middle of $w\}$ So the alphabet is $\{0,1\}^*$. My problem is that I can't keep track of the equality of chars before and ...
-1
votes
1answer
53 views

Building an undecidable T-Grammar

I am asked, "Show that these T-Grammars constitute a set of languages that are undecidable. Do this by building a T-Grammar for a Turing machine description. For a starting point you might think about ...
2
votes
1answer
75 views

Show that language generated by grammar is regular

We have grammar with nonterminals $ X_1,...X_n$ terminals $V_t$ and rewriting rules of form: $X_i \rightarrow a \in V_t $ $X_i \rightarrow X_jX_k, \ i \ge j , \ i > k $ How can I show that ...
2
votes
1answer
34 views

Explanation of Grammar Ambiguity

Consider now the grammar G S -> (S + S) S -> (S * S) S -> a Is it ambiguous? Answer: No because there are disambiguating parentheses and so no left or right recursion. Can someone explain how the ...
0
votes
3answers
85 views

What is the language generated by a given grammar

Given the grammar $s \to aSb \mid bSb \mid a \mid b$; what is the language generated by the grammar over the alphabet $\{a,b\}$? When I was solving this question I was a bit confused about the ...
-3
votes
1answer
45 views

CFG for the language “number of a's = number of b's + 2”

How can I construct a context-free grammar for the following language? $$ L = \{ w \in \{a,b\}^* : \#_a(w) = \#_b(w) + 2 \}. $$ Please help me out in this. I am not sure how to approach this ...
1
vote
2answers
58 views

Show that a language cannot be generated by linear grammar

I have a language $ L= \{ w \in \{a,b\}^* ; |w|_b=2i, i \ge 0 \}$ that is a language with even number of b's. I found a grammar for it with these rules: $S \rightarrow aS \ | \ bL \ | \ \lambda $...
3
votes
2answers
50 views

Meta-grammar for context-free grammars

Formal grammars like regular expressions (REs) or context-free grammars (CFGs) specify languages, i.e. sets of strings over an alphabet. Grammars themselves can be seen as languages, e.g. the set of ...
-1
votes
1answer
35 views

Could someone please explain this language to me and its grammar? [closed]

This is the problem: http://i.imgur.com/Io7h1en.png This was a problem I saw and I really have 0 clue what the Language means the (**) part, and its solution. I was wondering if anyone could please ...
-4
votes
2answers
110 views

odd length palindrome's f=language [closed]

Find the language generated by the following grammar over the input alphabet = {a,b}. S –> aSa | bSb | a | b The language generated by the above grammar over the alphabet {a,b} is the set of (A) ...
3
votes
1answer
88 views

Need for an augmented grammar

The question is under the concept of LR parser. Suppose the original grammar is S->AA A->aA|b Is it necessary to add an additional rule S'->S to make it as augmented grammar? In short, I want to ...
0
votes
0answers
42 views

Proof of completeness for CFG having twice as many zeroes as ones [duplicate]

One possible CFG containing twice as many zeros as ones can be, S -> 0S0S1S | 0S1S0S | 1S0S0S | ϵ (This CFG is redundant but it will do the job. So I am not interested in the redundancy. Other ...
0
votes
1answer
26 views

How to choose symbols to replace for this left-most derivation?

I have a context free grammar such as the following: $E→E+T | T$ $T→T×F | F$ $F→(E) | a$ Using the left-most derivation, the following can be derived: $E⇒E+T⇒T+T⇒F+T⇒a+T$ $⇒a+F⇒a+(E)⇒a+(T)$ $⇒...
1
vote
1answer
85 views

Why do we not use CFGs to describe the structure of lexical tokens?

This was an exam question for my course and I am struggling to actually answer it in a way that is not fluff. Here is my current answer: CFGs describe how non-terminal symbols are converted into ...
0
votes
2answers
71 views

Context free grammar for nested arrays separated by commas

I have to define a context free grammar for the following rules: (i) A pair of square bracket tokens [] surrounding zero or more values separated by commas. (ii) A value can be another array or a ...
1
vote
2answers
63 views

non LL(1) grammar but LL(1) language

I'm reading a Basics of Compiler Design and on page 84 it is making the following statement: A language may well be LL(1) even though the grammar used to describe it is not. Can someone give ...
0
votes
1answer
30 views

Is the given grammar LALR

We are given the following grammar. S-->AS/b A-->SA/a We have to tell if its LALR or not. As we all know that LALR is only minimization of CLR, So first I constructed the CLR parsing table using ...
4
votes
1answer
57 views

Is it decidable whether a linear language contains a square?

A square is a word of the form $ww$. A linear grammar is a CFG that has productions of the form $A\to uBv$ or $A\to u$ (with lower case symbols corresponding to terminal strings). Question: Is it ...
3
votes
0answers
60 views

Context-free grammar for DAGs?

I'm looking for a "safe" representation of DAGs. With "safe" representation I mean that it can be described by a context-free grammar. Ideally, this grammar would be suitable for a simple LR parser. ...
0
votes
0answers
17 views

why the end marker is part of a follow set of a start symbol?

I can't figure out why the end marker is part of the follow set of the start symbol, in other words if $\$$ is the input-end marker and $S$ is the start symbol then $ \$ \in Follow(S)$. My question is ...
4
votes
3answers
281 views

Is the set of CFGs that contain all odd and even length words Turing-decidable?

$ALLEVEN_{CFG}$ = {M is a grammar, and L(M) includes all strings of even length in $\Sigma^*$} = {(M): ($\Sigma\Sigma$)* ⊆ L(M)} $ALLODD_{CFG}$ = {M is a grammar, and L(M) includes all strings of odd ...
0
votes
2answers
38 views

Different between Left most and Right most derivation [duplicate]

I am a beginner started learning theoretical computer science.. I just came through. "Context free grammar" So my Question is that what is the different between Left most and Right most derivation. ...