Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
1
vote
1answer
67 views

Why is this language a regular language?

Came across this in a book, and I'm wondering why the following language is regular? $$ L = \{a^nww^R: n \geqslant 0, w \in \{a,b\}^3\}$$ Is it correct to say that $$ \{a^n : n \geqslant 0\} $$ is a ...
0
votes
2answers
29 views

Regular expression for a palindrome of finite length?

I have a language $$ L = \{ww^R, w \in \{ab\}^5\}$$ I know this is a regular language because it is finite (since w can only be of length 5). I want to prove it's a regular language, so I'd create a ...
1
vote
1answer
32 views

How to create a regular expression for this language?

I have a language: $$ \{a^jb^k \mid j \neq k \text{ and } j \equiv k \pmod 3 \}$$ I want to prove that this language is regular. My first thought was to create a regular expression that accounts for ...
0
votes
1answer
20 views

how to formally arrive at a correct EBNF grammar of a language

I am trying to write a mini parser for a simple language whose specification is as follows: A search term is represented by. Both searchkey and ...
-1
votes
1answer
25 views

Grammar with a long derivation generates an infinite language

Let $G$ be a CFG in Chomsky normal form that contains $b$ variables. Show that if $G$ generates some string with a derivation having at least $2^b$ steps, then $L(G)$ is infinite. This question is ...
0
votes
2answers
39 views

Is this an LL(1) grammar? How to solve First - Follow conflict?

im trying to check if this grammar is LL(1). S -> L = R L -> * L | id R -> L | R + R | num As you can see there is a Left recursion on R production. So i remove that and what i get is: S -> L = ...
0
votes
2answers
49 views

Is it possible to design a Turing Machine without extra symbols for this language?

Is it possible to design a Turing Machine for the language defined as L = {0n1n | n >= 0} with only the symbols in the set of {blank, 0, 1}?
1
vote
1answer
38 views

Context free grammar for $L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or } \vert u \vert_b \neq \vert v \vert_b\}$

I try to find a context free grammar for the language $L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or } \vert u \vert_b \neq \vert v \vert_b\}$. There is a hint ...
0
votes
2answers
60 views

Is the following language is a context free grammar language?

The question is to determine whether L is a context free grammar language, what do you think?
2
votes
2answers
79 views

Unambiguous context-free grammar for strings with at least as many a's as b's

I have designed this Grammar but it is ambiguous: $$S\to aSbS \mid bSaS \mid aS \mid\epsilon$$ Would anyone help me make it unambiguous? Assume the alphabet is $\{a,b\}$.
0
votes
0answers
40 views

Given a CFG and one of its nonterminals $v$ determine if there exists a sentential form beginning with $v$?

I am supposed to find an algorithm solving the following problem: Given a CFG $\;G=(V_N, V_T, R, S)$ and a nonterminal $v \in V_N$ determine if there exists a sentential form which begins with $v$. ...
1
vote
0answers
32 views

How to generate a DFA that recognizes a non-regular Grammar

How would you convert the following grammar to a DFA that recognizes its language? \begin{align} &G = (\{S,A,B\},\{0,1\}, S, P)\\ &P\colon &&S\rightarrow A1B\\ &&&A \...
1
vote
1answer
22 views

Is grammar that describes an equation in prefix (Polish) notation always unambiguous?

I recently completed a problem in which I was asked to generate a parse tree for the expression $+ \, 5 \, * \, 4 \, 3$ using the following grammar and rightmost derivation: $$Expr \rightarrow + \, ...
1
vote
1answer
19 views

Defining nullable symbols and the first set of a grammar

I'm practicing for an upcoming exam and am being tripped up by a review problem. The problem gives the following grammar: $$S \rightarrow AB\$$$ $$A \rightarrow \epsilon | a | (T)$$ $$T \rightarrow T,...
1
vote
1answer
22 views

Defining Grammar for Given Language

I'm attempting to practice for an exam and I'm having some trouble on one of the practice problems. The problem asks to identify a variety of language as regular grammar, context-free grammar, context-...
1
vote
1answer
18 views

Language of particular CFG

Let: $ G = <V, \Sigma, R, S >: \\ V = \{ S,A,B,C \} \\ \Sigma = \{0, 1\} \\ R: \\ S \to CSC|A \\ A \to 0B1|1B0 \\ B \to CB|\epsilon\\ C \to 1|0 $ I need to find the language (no need to ...
0
votes
1answer
21 views

Find CSG for $L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$

I am trying to find a context sensitive grammar for the type-1 language $L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$ I can construct the first part with \begin{align*} S &\to aSbB \mid B \...
0
votes
0answers
9 views

Writing a Grammar to a Language [duplicate]

is there a general method or approach to writing grammars to a language? I do not want to describe the language I have to write a grammar to as I do not want a specific answer. I am looking for ...
0
votes
1answer
16 views

What complexity class is this set of grammars? RE?

Given a grammar where every rule has the form $X \to YZ$, $XY \to Z$, $X \to a$, or $X \to \epsilon$ where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ ...
1
vote
1answer
28 views

What complexity class is this set of grammars? In between NL and P?

Given a grammar where (every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$), (($X \to YZ$) implies ($X \to ZY$)) and (($XY \to Z$) implies ($YX \to Z$)) where $X,Y,Z$ range over nonterminals ...
0
votes
0answers
14 views

What complexity class does is this set of grammars? L-complete?

Given a grammar where every rule has the form $X \to Y$ or $X \to a$ and (($X \to Y$) implies ($Y \to X$)) where $X,Y$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$...
1
vote
1answer
39 views

What complexity class is this set of grammars?

Given a grammar where every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$ where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, ...
0
votes
1answer
30 views

What complexity class does is this set of grammars? NL-complete?

The unrestricted grammars characterize the recursively enumerable languages. This is the same as saying that for every unrestricted grammar G there exists some ...
1
vote
1answer
45 views

Would the following grammar be ambiguous?

I have the grammar $S = aSbS|bSaS|\varepsilon$. When I was first looking at the problem I thought it was unambiguous. When I looked at the answer it said that it was ambiguous. The solution it gave ...
0
votes
1answer
38 views

Grammars and Parsing: Ambiguity in Sequences

BACKGROUND I am writing a grammar and parser for a domain-specific language. There is a specific form of expression that, while simple, is giving me headaches. Given terminals: "a": KEYWORD "b": ...
5
votes
2answers
524 views

Complement of a DFA without final states

Let $L_1=\{Q,\Sigma,q_0,\delta,Q\}$ be a DFA that accepts a language $L$ and where all the states are also final states. If we want a DFA that accepts the complement of $L$, we swap its accepting ...
0
votes
0answers
19 views

Grammar for $\{a^n b^m c^{n+m} \mid n,m \ge 1\}$ [duplicate]

Please help me solve this problem: Design a grammar for the language $\{ a^n b^m c^{n+m} \mid n,m\ge 1\}$.
2
votes
1answer
101 views

Is there a difference between the equivalent automaton of a grammar and an automaton which accepts the language produced by the grammar?

I have been assigned some homework in uni, related to push-down automatons (evaluated via final state, not empty stack) and context-free grammars. I have noticed that questions related to generating ...
0
votes
1answer
30 views

How can I determine the start non-terminal of a CFG?

Suppose I have a grammar such that there exist $n$ production rules which contain only terminal symbols, and none of these rules produce the same terminal (disjoint). $A ::= x|y|z$ $B ::= a|b|...
-1
votes
2answers
27 views

Finding the language generated by a grammar

Forgive my lack of knowledge, I am new. I tried to find the language generated by this grammar S → aA | bS | cS | ɛ A → aA | bB | cS | ɛ B → aA | bS | ɛ And I ...
0
votes
1answer
40 views

What is “σ” in a context free grammar?

I have a grammar like this: A → BAB | B | ε B → 00σ | ε What is the meaning of σ in the second rule?
1
vote
2answers
68 views

Difference between regular grammar and CFG in generating computation histories and $\Sigma^*$

I would like to ask for intuition to understand the difference between a CFG generating $\Sigma^*$ and a regular grammar generating $\Sigma^*$.. I got the examples here from Sipser. Let $ALL_{CFG}$ ...
1
vote
1answer
27 views

Why is $FOLLOW$ not necessary for $LL(1)$ grammars with no $\epsilon$ transitions?

I'm aware of how $FIRST$ and $FOLLOW$ sets are used to construct a parsing table for $LL(1)$ grammars. However, I've encountered this statement from my notes: With $\epsilon$ productions in the ...
0
votes
2answers
33 views

How to prove this language is context free?

There's lots of ways to prove a language is not context free. Going through some exercises, I'm stuck at a question that asks me to prove that a language is indeed context free. $L = \{a^{(n+1)} b^{(...
0
votes
1answer
18 views

Build LL(1) parsing table for grammar S -> iSeS | iS | a

Task Bulid parsing table for grammar S -> iSeS | iS | a Resolve conflicts in this table and simulate parser work for word ...
2
votes
1answer
126 views

What is the relation between parsing languages and checking languages?

I have looked at a number of textbooks on computability theory. They typically have the following form: Define a language class (regular, context-free, context-sensitive, recursively enumerable) ...
1
vote
1answer
36 views

How to construct a CFG which generates {0, 1, #}⁺ - {b_1#b_2#b_3#… #b_n | n is a whole number} where b_i is i in binary without leading zeros?

This problem was originally given in "Introduction to Automata Theory, Languages and Computation" by John E. Hopcroft and Jeffrey D. Ullman as Exercise 4.3. $$ \text {Let }b_i \text{ denote } i \text{...
2
votes
1answer
68 views

Formal Languages: if $L_1^* = L_2^*$, then $L_1 = L_2$

The question is: For all languages $L_1$ and $L_2$ , if $L_1^* = L_2^*$, then $L_1 = L_2$. We know that two languages are equivalent if $L(G_1) = L(G_2)$, where $L(G) = \{w \in T^* \mid S\Rightarrow^*...
0
votes
1answer
31 views

What kind of Grammar could this be

I am trying to sort Grammar into the Chomsky Hierarchy and I can do so for most of my examples but I am stumped by the following one: bX -> abY which Type of ...
3
votes
1answer
34 views

Minimizing DFA built on set of words

A set of English words is given. Is there linear or sublinear algorithm to build minimal DFA for the given dictionary? I tried different approaches, and they all were concerned with building Trie and ...
2
votes
1answer
39 views

Set notation of a grammar

Say I have a grammar e.g, $$\begin{align}S&\to AB\mid abc\\ A&\to aAb \mid \lambda\\ B&\to bBa \mid ba \end{align}$$ Now it is obvious the notation for this would be something like, $$L(...
10
votes
3answers
2k views

Representing “but not” in formal grammar

I just came across the following grammar definition: CommentChar ::       SourceCharacter but not LineTerminator But for discussion, I'll present this similar ...
0
votes
1answer
107 views

Table-Driven Lexer and the Classification Table

I'm trying to implement a compiler for a custom language as part of an assignment. I am still trying to figure out how to build the lexer. From what I understand, for a table-driven lexer, we have 3 ...
4
votes
2answers
934 views

Generating random words by grammar

A bit of context I was writing a parser for a grammar, and for testing purposes I come up with idea to generate some random inputs. The grammar I was dealing with was much more complicated, in this ...
4
votes
0answers
53 views

Reference on relating Post systems to string rewriting systems and formal grammars?

wikipedia states: Every Post canonical system can be reduced to a string rewriting system (semi-Thue system). [...] It has been proved that any Post canonical system is reducible to such a ...
0
votes
2answers
43 views

Formal grammar with constraints on the number of each symbol

I have a language where each type of symbol is only allowed a particular number of times, but the order isn't important. For example, lets say there are three symbols $a, b, c$, and a valid string in ...
0
votes
1answer
26 views

Determining recursive enumerability of given languages

I came across following problem: $L=\{M$ is a turing machine $M$ accepts two strings of different length $\}$ $L=\{M$ is a turing machine $M$ accepts atleast two strings of different length $\}...
1
vote
2answers
51 views

Is my grammar correct and context free?

I have this language $L = \{a^{n}b^{3n}c^{2m} : m,n \ge 1\}$. I have to determine a free context grammar that generates L. Looks easy BUT i have a question about the grammar I found. First things ...
0
votes
1answer
32 views

How to create CFG for $L := \{x| \#_0(x) \text{ is even and } \#_1(x) \text{ is odd}\}$

Create an CFG for all strings over {0, 1} that have the an even number of 0’s and an odd number of 1’s. Also, I have a hint HINT: It may be easier to come up with 4 CFGs – even 0’s, even 1’s, odd 0’s ...
-1
votes
1answer
29 views

Grammar for the following language: L = {$a^{k}$$b^{n}$$a^{m}$ : m,n,k $\in$$ N^{+}$ $\land$ m + k $\geq$ n}

I'm trying to create a grammar (having the highest type) for the language: L = {$a^{k}$$b^{n}$$a^{m}$ : m,n,k $\in$ $N^{+}$ $\land$ m +k $\geq$ n} I'm not finding any good approach for it. Hints ...

1
2 3 4 5
21