All Questions
Tagged with finite-automata formal-grammars
53 questions
3
votes
3
answers
254
views
Can one prove directly that the language given by a regular grammar is the language given by some regular expression?
The let $L$ be a language. The following are equivalent:
$L$ is given by a deterministic or non-deterministic finite accepter.
$L$ is given by a regular grammar.
$L$ is given by a regular expression.
...
- 177
1
vote
1
answer
238
views
Why is this grammar context-sensitive?
Working on: Richard Johnsonbaugh. (2018). Discrete Mathematics, 8/e (p. 607)
2. Determine whether the given grammar is context-sensitive, context-free, regular, or none of these. Provide all ...
- 139
3
votes
0
answers
125
views
Convert a regular expression to a *minimal* LL(1) regular grammar
Given a regular language defined by a regular expression, we can convert it to an NFA, which is equivalent to a right-regular grammar. The grammar is not generally LL(1).
However, if we convert the ...
- 151
0
votes
1
answer
34
views
Question about a grammar who generates $(0+1)^*$
On a test from my Automata theory class of last year, I have seen an excercise that gives the free context grammar $G$ with the following rules:
$$S \rightarrow 0S1 | S0 | 1S | \varepsilon$$
and asks ...
- 123
4
votes
0
answers
132
views
Constructing worst case for L* by D.Angluin
I'm working on constructing deterministic finite automata (DFAs) with a specific learning complexity when using the L* algorithm developed by Dana Angluin. My goal is to create a DFA of size ( n ) ...
0
votes
1
answer
53
views
Trouble proving this is regular
I'm taking an automata class and one of the examples is showing this is regular. My initial thought was to make a DFA to show it is but i'm a bit confused on what a DFA with a standard 5 tuple would ...
- 29
0
votes
1
answer
137
views
Simple description of the LR(0) table generator algorithm?
I have just implemented a parser on the relational database. Parsing is done with recursive query. Note: one commenter was misled by the word "recursive" before "query" to think &...
- 111
0
votes
1
answer
287
views
Why Regular Grammar is Left/Right Linear?
From the definition I know that regular grammar should be Left/Right Linear (ie it should have variable on Left/Right side of each production rules)
But, my question is why it is mandatory?
Can't we ...
1
vote
1
answer
120
views
Prove or disprove that $\{xc o(x) :x \in A\}$ is context-free, where A is a regular language
Suppose o is a map on strings to strings. For every language R, we let $o(R) := \{o(x) : x \in R\}$. If o(R) is a regular language for every regular language R, then prove or disprove that the ...
- 305
0
votes
2
answers
707
views
Design a CFG for $L=\{ w \in \{ 0,1 \}^* \}$, where $w$ contains at least three ones
$L=\{ w \in \{ 0,1 \} \}$ where $w$ contains at least three ones
Here is one solution for the productions:
$S \to A1A1A1A$
$A \to 1A | 0A | \epsilon$
However, now I have a question. Could I modify the ...
- 175
0
votes
0
answers
103
views
Languages with number of $a$'s a perfect square
Is there any finite automata ((N/D)FA, NPDA, DPDA, or any variation of a Turring Machine) that can accept the following language:
$\{s \text { is a string over } \{a,b\} \text { such that the number ...
- 141
2
votes
1
answer
168
views
Convert a dfa to rule for a asterisk case
Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
- 19
1
vote
0
answers
33
views
Has anyone seen the following string classifier discussed?
The closes related question I have found for this is Find string patterns preferably in regex for string streams, but it has no answer and is also a little less constrained as my idea.
Given a set of ...
- 111
-3
votes
1
answer
399
views
How can I convert from DFA in to regular grammar?
I have following information.
0 1
-> *q0 q0 q1
q1 q1 q2
q2 q2 q0
I have to convert this in to a regular grammar.
I wrote this:
...
- 11
-2
votes
1
answer
214
views
Finding the language generated by this grammar
I'm having problems with this. Can someone help me please.
Find the language generated by this grammar over the alphabet $\{0,1\}$:
$S\rightarrow BAB\mid CAB$
$BA \rightarrow BC$
$CA \rightarrow AAC$
...
- 3
4
votes
1
answer
326
views
Existence of a CFL $L$ such that $\sqrt{L}$ is not CFL
Does there exist a CFL L such that the language defined as $L' = \sqrt{L} = \{w | ww \in L\}$ is not CFL? I feel that there is no such $L$ but obviously, I am unable to prove it.
I am sorry but I have ...
- 281
3
votes
1
answer
2k
views
Is there a method to generate the complement of a context-free grammar?
Given the languages $L_0 = {w \in \{0,1\}^*}$ such that $w$ is a palindrome and $L_1 = {w \in \{0,1\}^*}$ such that $w$ is not a palindrome, meaning $L_1$ is the complement of $L_0$, we want to find ...
- 1,153
3
votes
1
answer
3k
views
What does it mean for a grammar to be LR(0)?
I am unsure what it means for a grammar to be $X$. More specifically, what it means for a grammar to be LR(0).
For part of an assignment I had to form the DFA for a grammar, which I had no issues with....
- 156
1
vote
1
answer
169
views
How do you create a sentential form in a given grammar?
I am given the following grammar:
$$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | ϵ | S$$
I need to decide whether $aBaabda$ can be produced in the given grammar.
I am unsure how the grammar can ...
- 156
1
vote
1
answer
27
views
Definiton of a certain symbol in a proof(The right linear languages are exactly the finite state languages)
I want to stress that i am not looking for a proof of this question, but rather if someone(that is familiar with the proof and it's context) can explain to me what the symbol 'e' means in the context.
...
- 217
3
votes
1
answer
138
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 ...
- 45
0
votes
2
answers
2k
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 ...
- 45
1
vote
1
answer
61
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 ...
- 45
1
vote
0
answers
190
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 \...
- 111
0
votes
2
answers
671
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^{(...
- 125
3
votes
1
answer
241
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 ...
0
votes
1
answer
3k
views
What does {a,b}* for DFA's mean?
For instance when the question contains $\{a,b\}^*$ does this mean that the DFA must have at least one $a$ and one $b$ on top of whatever conditions it has?
For example a DFA that accepts $\{w \in \{a,...
-1
votes
1
answer
82
views
Constructing a DFA of strings that are in A but not in B
I am tasked with creating a DFA for the regular language L = A/B, which are the strings that are in A but not in B. The alphabet is Σ = {a,b,c}
I am not really sure where to even start with this one, ...
0
votes
1
answer
192
views
Create automata from non regular grammar
I have two grammars:
L → ε | aLcLc
L → ε | aLcLc | LL
This two grammars are equals but the first one is regular, so it produces a regular language and a ...
2
votes
2
answers
559
views
Can a Formal Language be of a type (RE, REC, Regular, etc) for one TM, but of a different type for another?
I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this ...
4
votes
1
answer
3k
views
Understanding application of Arden's theorem to find regular expression
I learnt Ardens theorem and its usage as follows:
Ardens Theorem
Let $P$ and $Q$ be two regular expressions over alphabet $Σ$. If $P$
does not contain null string, then $R = Q + RP$ has a ...
- 1,727
2
votes
1
answer
708
views
Are grammars corresponding to DFAs unambiguous and those to NFAs ambiguous?
Are grammars corresponding to DFAs unambiguous and those to NFAs ambiguous?
According to what I studied, every DCFL is guaranteed to have an unambiguous grammar though there are multiple grammars ...
- 189
0
votes
0
answers
38
views
Find any kind of grammar for the language
Find any kind of grammar for the language L = {w ∈ Σ* | in w there
are twice as many a's than b's} and reason its correctness.
Where ...
- 167
0
votes
1
answer
8k
views
Construct an equivalent NFA for the given regular grammar
Given is the regular grammar G = ({A,B}, {a,b}, P, A) with the rules
P : A → aB, a, ε (where ε is the empty word)
B → bA, b
...
- 167
2
votes
4
answers
8k
views
DFA accepting strings with at least three occurrences of three consecutive 1's
The problem states the following:
Draw a deterministic finite automaton (DFA) accepting strings containing at least three occurrences of three consecutive 1's on alphabet $\Sigma=\{0,1\}$ with ...
- 1,727
0
votes
0
answers
2k
views
How to construct regular grammar (right linear and left linear both) from regular expression?
I am interested in some kind of algorithm to achieve this.
Basically here is the regular expression aa*(ab+ a)* and I want to construct a regular grammar for this....
14
votes
2
answers
3k
views
How did the word "production" end up being a synonym with the word "rule" in the context of Computer Science?
I am studying formal languages and production bases systems (rule-bases systems) and I am a little confused about why do these two word "production" and "rule" mean the same thing in so many context ...
- 818
0
votes
1
answer
197
views
How to write a regular expression to match a string that starts with the same pattern that it ends with
Let's say we want to write a regular expression that matches a string that ends with the same pattern that it begins with.
Let's say that we have an alphabet composed of the binary symbols: {0,1}
We ...
- 818
1
vote
2
answers
2k
views
A context-free grammar for a language of strings with occurrence properties?
Creating a context-free grammar for the language
$L_1 = \{ 0^{n} 1 ^{m} \mid m,n \in \mathbb{N} \wedge m \equiv n \mod 3\}$
is quite easy. A grammar is
$$ S \rightarrow \epsilon \mid 0A $$
$$ ...
- 179
8
votes
1
answer
2k
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 ...
- 309
1
vote
1
answer
147
views
Calculi for a computability class
Proving two push down automata equivalent is undecidable. But proving two finite state machines equivalent is decidable. You also cannot write a programming language that allows expressing the ...
- 459
0
votes
1
answer
959
views
Why is $L=wxw^R|w,x\in\{0,1\}^+$ regular? [duplicate]
I was taught that if you can create a DFA to accept a language, then the grammar that is generating the language is regular.
AND
A DFA is a finite automata that accepts a language and also rejects ...
2
votes
1
answer
113
views
Using Context free language to simulate regular expression in finite automata
Is there a minimum number of non terminal we need to use in order to simulate a finite automata with n states? When we try to convert a language accepted by NFA to context free language, do we need n ...
- 61
1
vote
1
answer
1k
views
How to remove empty strings a.k.a (lambda, epsilon) from a LR(0) grammar
Say I have the following grammar:
E -> TE'
E' -> +TE'| -TE' | λ
T -> (E) | id
I need to build the finite state machine with the LR(0) items,
But I ...
- 181
4
votes
1
answer
245
views
Language of walks in a grid – context-free?
Consider the infinite two-dimensional grid with integer co-ordinates. A walk in the grid can be represented by a string over the alphabet $\{u,d,l,r\}$, where the letters stand for moving one square ...
0
votes
2
answers
4k
views
Converting regular (Type-3) grammar to a deterministic finite state automaton
I would like to create a deterministic finite state automaton (DFA) M=(Q, Σ, δ, q0, F) that is accepting the language generated by the following regular grammar (RG) G=(N, Σ, P, S). In short I want to ...
- 121
1
vote
1
answer
345
views
Is it Regular Language?
According to Wikipedia, Regular Language is Recognized by Some DFAs, or expressed by Regular Expression .. and all finite Language are regular but, not all regular is finite ..
that's mean it may be ...
- 135
1
vote
1
answer
1k
views
Regular and not Regular Grammar
According the Peter Linz Book, am a confusing about the two example
the Grammar G1 = ({S},{a,b},S,P1) with P1 given as
S -> abS|a
and G2 = ({S,S1,S2,},{a,b},S,P2)
S -> S1ab
S1 -> S1ab|S2
S2 -> a
...
- 135
-2
votes
1
answer
94
views
Language of a grammar
What's the language of following grammar?
$G: S \to S_1B$
$S_1 \to aS_1b$
$bB \to bbbB$
$aS_1b \to aa$
$B \to \lambda$
any hint or solution?
- 19
0
votes
3
answers
6k
views
Build a regular grammar for a regular language [duplicate]
The language considered is the infinite set of all chains that meet the following conditions.
Conditions:
...
- 135