Questions tagged [automata]
Questions about mathematical devices that read an input stream symbol by symbol and use a state transition map to produce an output stream, maybe using secondary storage.
1,198
questions
0
votes
0answers
23 views
why does the pumping lemma want us to only consider the first repitition of states?
In Sipser's Intro to Theory and computation, He writes:
I don't understand the constraint on x. Shouldn't it be just y <=p? (Equal bc in the case when machine M runs through all states p) Making ...
-1
votes
0answers
16 views
Formal languages of automata [on hold]
Im having difficulties understanding this question that revolves around context-free language.
2
votes
1answer
17 views
Pumping Lemma for Regular Languages with 3 variables (a^nb^mc^m)
I've been trying to understand the pumping lemma, and how to apply it to a language such as a^nb^mc^m where n >= 0 and m >= 0. The pumping lemma states that:
For any regular language L, there exists ...
0
votes
0answers
19 views
Is this language Deterministic?
I came across this question in Peter-Linz today,
Is the language L= { a^nb^n : n>=1 } U {b} deterministic ?
My doubt is that say we have a case like this {a^5 b^6} U {b}, after popping 5 a's from the ...
1
vote
1answer
45 views
How to characterize equivalence classes induced by Myhill-Nerode theorem?
Given $L=\lbrace w\in \lbrace 0,1 \rbrace^\ast : N_0(w)=N_1(w) \rbrace$, where $N_0(\cdot)$ and $N_1(\cdot)$ mean the number of zeroes and ones respectively, I need to characterize the classes ...
0
votes
1answer
39 views
find derivation trees for CFG
I need to draw the derivation tree for $1-2-(3-4)*5*6$ from the grammar below.
I want to know how many possible derivation trees are there from this grammar.
$$\begin{align}V_n&=\{expr,term,...
0
votes
0answers
29 views
1
vote
1answer
50 views
Can CYK Parsing algorithm generate the parsing tree in O(n^3)?
I found this question What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity? saying CYK Parsing algorithm can compute any Context Free ...
0
votes
1answer
26 views
Language which is recursively enumerable but not recursive [duplicate]
Can someone provide me with some examples of languages which are recursively enumerable but are not recursive. I know that there exist some languages which are not Recursive but recursively enumerable ...
0
votes
0answers
28 views
Does SLR(0), LALR(0) exists?
I read about LL(1), LR(0), SLR(1) and LALR(1) in many online sources and even in dragon book. However I found that no one talks about LL(0), SLR(0) and LALR(0). So I googled and come up against these ...
0
votes
1answer
20 views
Getting from one language to the other using closure properties(automata) [duplicate]
I am trying to deduct how i can, using closure properties, deduct that since the following language is not context free $$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}...
-1
votes
0answers
7 views
Convert CFG into Greibach then to PDA
(I don't know how to convert to PDA (b))
S→aAb|bAa|aSb|bSa
A→aAa|lambda
a)Convert the following CFG into equivalent CFG in Greibach normal form
b) Resulting grammar from a) convert to PDA
2
votes
2answers
67 views
Using pumping lemma to show a language is not context free(Complicated)
How can i show that the following long language is not context free using the pumping lemma?
$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}...
0
votes
1answer
28 views
Construct NPDA for the language
$L=\{w \mid w \in \{a,b\}^*$, $\text{the number of a's is at least the number of b's} \}$
I'm stuck trying to build an NPDA that accepts $L$.
2
votes
2answers
29 views
Given an non-deterministic finite automaton, will its determinization always have unreachable states?
Given an NFA that accepts the regular language L, will its equivalent DFA which accepts the same language L always have unreachable states.
If it does, why?
0
votes
1answer
22 views
Counting number of states from a regular expression
Given the regular expression: $r=ab+((a+\epsilon)c^*)^*$.
Let A be a non-deterministic automaton that accepts the language of r.
How many states are in A?
Answer the question without building A ...
0
votes
1answer
25 views
How making non LL, non LR grammar a valid LL grammar, also makes it a valid LR grammar? Is there any connection between LL and LR conflicts?
I might unncecessarily overthinking here, but I had this weird possibly meaning less doubt:
When grammar is neither LL nor LR, it means, both LL and LR parsing tables involve conflicts. LL parsing ...
1
vote
1answer
39 views
what is the difference between transition function (delta) and extended transition function (delta cap ) in finite automata
my doubt is
what is the difference between transition function (delta) and extended transition function (delta cap ) in finite automata ?
both of them when started at a state q for a string w will ...
3
votes
1answer
33 views
Are the languages recognized by deterministic one-counter machines equivalent to deterministic context free language?
In Introduction to Automata Theory, Languages, and Computation, John Hopcroft mentioned[1]
In fact, a PDA In fact the languages of one counter machines are accepted by deterministic PDA's although ...
0
votes
1answer
21 views
Prove that the language L = {w1, w1w2, w1w2w3, ..} is regular, provided wi is in a regular language
Let's assume that we're working over a finite alphabet $\Sigma=\{a, b\}$. How can one prove that $$L_2=\{w_1w_2...w_m| m ∈ \mathbb{N}, ∀i(w_i ∈ L)\}$$ is a regular language, provided that L is regular?...
2
votes
0answers
68 views
Intersection of two deterministic parity automata
Given two deterministic parity automata $A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$ and $A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$ with the finite set of states $Q_i$, the finite alphabet $\Sigma_i$, the ...
2
votes
1answer
21 views
Help with figuring out if MAX(L) is a CF language
We call the word $x_1$ a true prefix of the word $x$, if a non-empty word $x_2$ exists so that $x=x_1x_2$. For the language L (over some finite $abc$..). We define MAX(L) as:
$MAX(L)$ = {$w_1 \in L $|...
-1
votes
0answers
18 views
How to precisely know whether a language is regular ? , a regular expression can be generated for it ? , as well as dfa? [duplicate]
I feel difficulty in finding whether a language is regular and also is regular expression can be generated ??
Please anyone let me know about all the possible cases.
This will help me very much..
1
vote
1answer
52 views
Can the difference of a non-regular and a regular language be regular?
I have some trouble understanding some exercises related to operations on regular languages.I tried to apply their closure properties, but I am not sure how to do the following exercises:
If $L_2,L_3$...
2
votes
2answers
44 views
Is the language L = {(a,b)* | #a * #b is an odd number} regular?
Is the following language regular? $$\{ w \in \{a, b\}^* |\ \text{the product of the number of $a$'s and the number of $b$'s is an odd number}\} $$
If i'm not mistaken the condition is the same as ...
2
votes
1answer
44 views
Construct a DFA from the regular expression (a)*+(aab)*
I've broken down the expression into two simpler DFAs but right now I'm stuck.
I don't know what to do with the expression a*, my solution currently (as presented above) is a NFA, not DFA.
2
votes
1answer
18 views
Proving a language comprised of 2 languages is regular(with suffix and prefix)
I am having hard time proving that the following language,comprised from two regular languages $L_1,L_2$(over the same $\Sigma$)is indeed regular:
$$L^\frown = \{ w\in \Sigma^* | w=u\sigma_1\mu_1...\...
4
votes
1answer
23 views
Proving a language comprised of 2 languages is regular
So glad to find this place. I have been struggling for quite a while with this given question and i am not sure how to fully address it.
The question:
$L_1$ and $L_2$ are regular languages over the ...
5
votes
1answer
46 views
Two languages such that $L_1 \cup L_2 \leq_m\, L_1 \cap L_2$ and two (other?) such that $L_1 \cap L_2 ≤_m\, L_1 \cup L_2$?
Are there languages $L_1$, $L_2$ such that such that
$$L_1 \cup L_2\leq_m\, L_1\cap L_2,$$
and two other languages such that
$$L_1 \cap L_2 \leq_m\, L_1 \cup L_2?$$
And if so, what are they? How ...
1
vote
0answers
24 views
How to visualize non-deterministic pushdown automata?
My friend and I are working on this project for our Formal Languages and Automata class that consists in building a pushdown automaton. A part of the project that is bothering me is how to visualize ...
1
vote
1answer
34 views
Unambiguousness and determinism of CFGs for them to be LR
I came across this statement:
Note that there are unambiguous grammars for which every LR parser construction method will produce a parsing action table with parsing action conflicts.
I was ...
1
vote
1answer
57 views
Connection between non determinism and LL(1) conflicts
I am trying to understand connection between non determinism of grammar and LL(1) conflicts introduced by it.
As per my understanding non deterministic context free grammar is a context free grammar ...
1
vote
0answers
25 views
Tree languages regular
Let $T_1,T_2 \subseteq T_\Sigma$ be regular tree languages, f a symbol with arity 2.
To proof: $\{f(t_1,t_2) \mid t_1 \in T_1, t_2 \in T_2\} \subseteq T_{\Sigma \cup \{f\} }$ is regular.
So it's ...
3
votes
3answers
86 views
CFG for all strings of a’s and b’s that contain a different number of a’s and b’s
I am trying to write CFG for all strings on {a,b} that contains different numbers of a’s and b’s? After two hours of brainstorming, I came up with this:
S→A|B
A→aE|aA|EA
B→bE|bB|EB
E→aEbE|bEaE|Λ
...
2
votes
2answers
34 views
Examples of infinite sets of regular and non-regular languages that their union is regular and non-regular
I have been looking around for a good source to answer the following question.
Have read a few different sources but have not found the answer I was looking for.
The question is:
Give an example ...
2
votes
1answer
83 views
Finding a regular expression of a language
Our alphabet is {a,b} and we need to find a regular expression for the language of all words of the form $a^*b^*$, whose length is a multiple of 3.
Obviously $(aaa)^*(bbb)^*$ is one of the options, ...
0
votes
1answer
38 views
Prove or disprove the following proposition $L_1^*∪L_2^*⊆(L_1∪L_2)^*$ [duplicate]
$L_1^*∪L_2^*⊆(L_1∪L_2)^*$
I actually disproved the opposite proposition $[(L_1∪L_2)^*⊆L_1^*∪L_2^*]$ and my intuition tells me that this is actually true... I tried to show that the combinations of ...
0
votes
0answers
31 views
Understanding handle, viable prefix and valid item in the context of LR(0) and LR(1) items
Dragon book gives definition of handle, viable prefix and valid item at various different places. I am trying to understand these definitions in each other's context. Various definitions given are as ...
1
vote
1answer
59 views
When will SLR(1) parser fail but CLR(1) will not
Dragon book says following about where SLR(1) parser can fail but CLR(1) wont:
Recall that in the SLR method, state $i$ calls for reduction by $A→α$ if the set of items $I_i$ contains item $[A→α.]$...
1
vote
0answers
58 views
What is the word “madness” doing in the first chapter's title of Automata Theory, Languages and Computation by Hopcroft, Motwani, Ullman?
The chapter's title is "Automata: The Methods and the Madness". This title came along in the second edition and remains in the third edition. In the first edition, the the second chapter's title is "...
0
votes
0answers
14 views
building turing machine for busy beaverproblem
I have tried to build a turing machine for busy beaver problem that has BB(2,3) two variables and three variables but i am not sure if its correct or it needs any changes
0
votes
0answers
26 views
Using Nerode theorem to prove that the following languages are non-regular
I've been trying to understand the idea behind proving a language is not regular by using Nerode's theorem, but I just couldn't apply the idea on what I've been asked.
The problem is to prove the ...
2
votes
3answers
62 views
proving L1* ∪ L2* ⊆ (L1∪L2)*
x∈ L1* ∪ L2* ⇔ x∈ L1* ∨ x ∈L2* ⇔ x ∈(L1)* ∨ x∈(L2)* ⇔ x ∈L1* ∪ L2* ⇔ x∈(L1∪L2)*
Is it enough to prove it this way?
2
votes
1answer
58 views
In what sense a type of parser is less power than the other?
I am learning LR(0), SLR(1), CLR(1) and LALR(1) parsers.
I know how parsing tables of each of them is formed. If x < y means parser x is less "powerful" that parser y, then, I read, the ...
1
vote
1answer
45 views
MSO (Monadic second-order logic) Logic On Words
Let L be a language over $\Sigma = \{a,b,c\}$ that contains all words, where the length $|w|_b$ (number of all b's) has remainder 1 if divided by 3.
MSO logic over words are definded as follow:
I ...
1
vote
1answer
70 views
I have trouble translating Turing machine language, can you help me break down language notation to English?
My problem is I don't have many issues with creating a Turing machine state table when given a string such as 01101, my issue arises when I am presented with a problem which requires the Turing ...
0
votes
0answers
14 views
Connection of relation between valid item and viable prefix with canonical collection
I was trying to understand connection between different concepts of parsers and how those are followed in actual parsing steps. I came across following statement while reading LR parsers:
An item ...
0
votes
1answer
44 views
Dana Angluin's L* algorithm - Hypothesis inconsistent
is it possible for the Dana Angluin's L* algorithm that a hypothesis is inconsistent?
So assume we have a closded observation table for a regular language L. Now after creating the hypothesis we will ...
0
votes
2answers
52 views
Prove that the following language is regular [duplicate]
Let L1, L2 be regular languages. And let A1=〈Σ,Q,q0,𝛿1,F1), A2=〈Σ,P,p0,𝛿2,F2) be their DFA.
Prove that the following language is regular, by making an appropriate NFA for it:
𝐿3={𝜎1𝜎1′𝜎2𝜎2′…𝜎...
1
vote
0answers
27 views
Computational power of quantum finite automata
I am preparing some lecture notes on the computational power of quantum finite automata (QFA). I am a bit confused about which models of QFA are stronger and which models are weaker than standard ...
