Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
1,093
questions
0
votes
1answer
64 views
Design a CFG that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }
I am trying to design a context-free grammar that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }.
This is really confusing me, I'm having trouble with ...
-1
votes
1answer
34 views
How to find the language and create Push down automaton if the A is continuously looping ? and will PDA accept L produced without A
Let us consider the following Context-Free Grammar
G = ({S,A,B,C,D},{a, b}, S, P)
with production rules P:
S → SSA | Bb
A → BSA
B → A | Cb
C → AD | Cb | ɛ
D → a | b | ɛ
Let L be the language ...
3
votes
1answer
126 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
74 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
41 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
28 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 ...
-2
votes
1answer
144 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
258 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
60 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
61 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
71 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
128 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
42 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
44 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
109 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
211 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
63 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
24 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
29 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
22 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
56 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
15 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
45 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
46 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
69 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
39 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
620 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
21 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
132 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
123 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|c$
...
$...
-1
votes
2answers
34 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
55 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
160 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
78 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
44 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
69 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
137 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
46 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{...
3
votes
1answer
91 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
60 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
112 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
299 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
1k 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
57 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
48 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
45 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
77 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 ...
