abstract lotus
so im following a question bank and i came across these questions whose answers werent given in my study notes , perplexed I went to chatgpt and google no luck hopefully maybe you guys can help , but i think these questions are incomplete cause they make absolutely no sense
obsidian spokeBOT
so im following a question bank and i came across these questions whose answers ...
+close
Feel free to nominate the person for helper of the week in #helper-nominations
If you're happy with the help you got here, and the server overall, you can contribute financially as well:
abstract lotus
the highlights were made by me btw
lucid matrix
so you're talking about 4 and 5 ? @abstract lotus
abstract lotus
4 5 and 6
abstract lotus
so you're talking about 4 and 5 ? <@455646210099904512>
cause i have no clue what any of them r referring to
abstract lotus
yeah but the question bank is divided as per modules the first module is regarding sets and the 4th are concerning automatas , you reckon they mixed them up?
lucid matrix
yes
lucid matrix
and 4 and 5 is just: find the dfas for the following languages
(it would be the most sensible interpretation)
abstract lotus
oh so a finite language could also be referred to as a dfa?
lucid matrix
no
what I say is that a finite language is regular, so can be recognized by a dfa
(a language is not a dfa)
(maybe I'm nitpicking on vocabulary and you already understood)
abstract lotus
hmph dont we need a condition to construct a dfa? i dont see one for 4
abstract lotus
like it should end in ab or smth like that i'm quite foreign to the subject
lucid matrix
no
abstract lotus
like how do we construct a dfa for question 4 with the language alone , ive never done that before
it's usually paired with a condition like "string should end in 00"
lucid matrix
do you have examples in your lecture notes ?
abstract lotus
yep one moment
lucid matrix
it's usually paired with a condition like "string should end in 00"
not at all
lucid matrix
yes, L = {strings on {a,b} ending with ab} is one instance of a regular language
but it is just one example
for instance, do the following one: {strings on the alphabet {a,b} only containing a's}
(the question you need to ask yourself when constructing the automaton is: if I am given the letters from start to finish, how do I check the condition using finite memory ?)
abstract lotus
for instance, do the following one: {strings on the alphabet {a,b} only containi...
well there would be two states q0, q1 if it's a move on to the next state terminate if it isnt stay on q0?
so I guess the 4th condition is asking us to interpret the language and figure it out by ourselves?
lucid matrix
well there would be two states q0, q1 if it's a move on to the next state termin...
describe explicitly the automaton, what are the starting state, accepting state and transitions ?
abstract lotus
hmph since it's not explicitly mentioning an alphabet do we just take the contents of L as alphabet?
lucid matrix
I think the alphabet is implicitly {a,b}
abstract lotus
describe explicitly the automaton, what are the starting state, accepting state ...
q0 is the initial state q1 is the accepting state
DFA is the automaton
idk how to do the squiggly symbol on qwerty :/
{q0,a}=q1
{q0,b}=q0
abstract lotus
I think the alphabet is implicitly {a,b}
hmph alright
lucid matrix
q0 is the initial state q1 is the accepting state
DFA is the automaton
idk how...
that's wrong
abstract lotus
ah
abstract lotus
for instance, do the following one: {strings on the alphabet {a,b} only containi...
I was trying to answer this one
lucid matrix
ok
abstract lotus
is it incorrect?
lucid matrix
yes, your current solution is incorrect
abstract lotus
hmph
lucid matrix
for instance, try to input aa, what happens ?
lucid matrix
that's not good either, because then aa is not accepted
lucid matrix
try to do it by hand
how would you check (by hand, or by writing a computer program) that all the letters are a ?
abstract lotus
id look at all the values and if i come across a b id deny it
lucid matrix
exactly
abstract lotus
through a loop statement and a decision one
lucid matrix
now try to express it as an automaton
lucid matrix
so, say that q0 is the first state
abstract lotus
mhm
lucid matrix
yes
so what you do is to go to a ditch state q1
so you add the transition q0 -b-> q1
q1 will loop on itself, because whatever letter you read after, it doesn't matter : you read the letter b somewhere, so the word does not belong to the language
so you have the transitions q1-a->q1 and q1-b->q1
abstract lotus
so you make two separate machines?
lucid matrix
you make two separate states
q0 means "I have not yet read a b"
q1 means "I have read a b"
you start at q0, and you accept if in the end you remain in q0
abstract lotus
ah
lucid matrix
q1 plays that role
abstract lotus
I think i kinda get it now
erm moving on to the 5th question do we just directly take the strings inside the Language and express them as states? like for the first one q0 --a--> q1 end something like that? if so how would it work for L=(a,b)?
lucid matrix
(this is what you should get for my question)
abstract lotus
Oh my that's so much better
yeah okay I guess my assumption was correct then
but I'm still a bit confused on what a language represents
lucid matrix
a language is just a set of words
a common problem in computer science is deciding given some description of a language L and a word w whether w belongs in L
this is called the word problem
abstract lotus
hm so a word such as abba wouldnt be accepted since L can only have A's something like that?
lucid matrix
in your current lecture, you are studying languages for which the word problem can be decided using a deterministic finite automaton (dfa)
lucid matrix
hm so a word such as abba wouldnt be accepted since L can only have A's somethin...
yes, so now try to input it in the automaton I gave you to understand how it is treated
abstract lotus
in your current lecture, you are studying languages for which the word problem c...
we've also got ndas as well which I think take input to more than 2 states or smth like that
abstract lotus
yes, so now try to input it in the automaton I gave you to understand how it is ...
well a would go back into a then b would go to q1 where it would lie before it ends
this is the only example we have of ndas
OH WAIT
an nda can have two conditions whereas a dfa can only have one
is that correct?
lucid matrix
no
abstract lotus
ow
well that's how I see like for example if we take the example above it can accept both 00 and 11 I dont think you can do that with a dfa unless im wrong
lucid matrix
dfa can do everything nfa can do
abstract lotus
mhm
lucid matrix
but I think that given your current level of understanding you should first stick to dfa's
otherwise it will only be more confusing
abstract lotus
well I kinda got an exam tomorrow and I'm only struggling with NFAs
and the two questions above
perhaps you could give me a surface level explanation?
lucid matrix
dfa: for each state q and letter a, there is exactly state q' such that q -a-> q'
nfas can have multiple transitions from a state labelled by the same letter
for dfas, you accept if the only sequence of transitions terminates in a terminal state
for nfas, you accept if at least one sequence of transitions terminate in a terminal state
abstract lotus
this is the only example we have of ndas
so here 0 can either transition to the state its already in or q1 something like that?
lucid matrix
yes
abstract lotus
ah okay
lucid matrix
00 is accepted because it labels the sequence of transitions q0 -> q1 -> q3
(where q3 is terminating)
it also labels q0->q0->q0 with q0 not terminating, but it doesn't matter
abstract lotus
but it could also stay in q0 and still be accepted
yeah sweet
i think i get it now
lucid matrix
it doesn't matter because you have at least one sequence of transitions labeled by 00 going to a terminal state
abstract lotus
yep
abstract lotus
(this is what you should get for my question)
howd you make this btw? like did you use a site?
lucid matrix
I used ipe
it is a free vector drawing tool
which can also be used to do slides
I use the pc version, but there is also an online one https://ipe-web.otfried.org/index.html
abstract lotus
oh thanks
hm could you explain the 5th one to me I dont think i quite understand it
lucid matrix
do the same
how do you check that some word w = w1…wn is equal to some fixed word u1…uk ?
abstract lotus
uhm for the first one check if it's a if so stay otherwise if its b (assuming) go to q1 and let it stay there?
abstract lotus
(this is what you should get for my question)
like this
and the second one is just one state with a,b looping on it
lucid matrix
yes, so for each i, you have state qi which says "the first i letters are good"
you then add a sink state q' "there is too much letters, or one of the first letters is wrong"
from this, find the transitions
(take your time)
abstract lotus
what I'm confused with is why theyd even ask a question like this when theyve never even attempted to teach something as complicated as this ik it really isnt complicated but when you have incompetent professors who just ask you to copy off a pdf blindly what are you supposed to do
im currently doing the other questions ill send you a ss once im done
lucid matrix
what I'm confused with is why theyd even ask a question like this when theyve ne...
isn't this the exercise sheet of your first lecture ?
abstract lotus
isn't this the exercise sheet of your first lecture ?
nah mate they send us pdfs to study for the exam , they dont even give us books!
and they ask questions out of them
lucid matrix
how long did you have this pdf ?
abstract lotus
the questions? for like a week id say
the professor hasnt even bothered to respond to my questions
so i gave up
lucid matrix
well I kinda got an exam tomorrow and I'm only struggling with NFAs
and you already have an exam ???
after a week ?
abstract lotus
yeah , thankfully its not difficult though , I feel like such a moron honestly , I shouldnt have joined this college , its filled with morons who still fail after receiving the question paper
and professors whod rather let their students play videogames than actually teach anything
it's so unserious
lucid matrix
doesn't matter, maybe find some group of students you can study with, it would be more motivating
abstract lotus
doesn't matter, maybe find some group of students you can study with, it would b...
definitely I'm exhausted by how literally my entire class shares the same sentiment , like they arent ill-natured or anything they're just demotivated and have no incentive to study I wish i went abroad instead , and i couldve but my parents are paranoid , im sorry if im going on a tangent
lucid matrix
yeah, I can only give you generic advice here
abstract lotus
yeah, I can only give you generic advice here
which i really appreciate
I'm just really anxious
ik you're waiting on me to finish the 2 questions but its getting a bit late here you mind if i send them tomorrow? im trying to finish the last module
lucid matrix
yes, no problem
abstract lotus
cheers
lucid matrix
don't worry too much, it is probably some quick test
abstract lotus
don't worry too much, it is probably some quick test
well its for a 100 marks it's definitely not quick it's an end sem none of the teachers have taught as anything
funnily enough they slack off more than the students which is impressive
also im sorry if im asking for a lot here , but could you give me the answers to two questions?
would you mind me asking? i hope there isnt a hand holding policy here
lucid matrix
wtf is your college ?
lucid matrix
you then add a sink state q' "there is too much letters, or one of the first le...
I gave you the indication here
abstract lotus
wtf is your college ?
somewhere I dont belong 😄
abstract lotus
I gave you the indication here
oh no its a diff one
im gonna do those two linked in this post tmrw
its the NDAs im not really sure whether ive done them correctly
and i have no example to base them off of
i did the dfas flawlessly though
well 4,6 are the same
just switched the letters for numbers
so if you could do either one of them then i could check if im correct
lucid matrix
dfas are particular cases of nfas, so you're good
for 4, isn't that just words with at least one letter ?
abstract lotus
wym
it's input which ends in either 1 or 0 so something like 01 10 100 101
or thats how im interpreting it
lucid matrix
I do too, but any nonempty word on the alphabet {0,1} ends with either 0 or 1…
abstract lotus
I do too, but any nonempty word on the alphabet {0,1} ends with either 0 or 1…
which doesnt make sense and here I thought I was missing something
the questions r so unnecessarily vague
lucid matrix
ok, you can try to answer this question instead
to train
construct a nondeterministic finite automaton accepting all strings over {0,1} that end with a nonempty sequence of 0's followed by a nonempty sequence of 1's
abstract lotus
what do you mean by a nonempty sequence?
lucid matrix
well technically, the empty word ε is an empty sequence of 1
what I want is binary words of the form w 0…0 1…1 with 0…0 containing at least one 0, and 1…1 containing at least one 1
@abstract lotus
abstract lotus
what I want is binary words of the form w 0…0 1…1 with 0…0 containing at least ...
alright I'll try it out and ill come back to you thank you for being patient with me im really dense
abstract lotus
@lucid matrix my exam went quite well! I got every question correct as per the study guide , the transition diagram question appeared and I drew like 6 different machines hopefully the examiner is lenient since the question was really vague
lucid matrix
ok, good for you
steady sphinxBOT
@abstract lotus
steady sphinxBOT
Thank you for your feedback! pétaire has been awarded 1 
. They now have 829 . They have 2 daily left for today.
