theory of computation practice problems

<2024-10-07 Mon 19:50:04>
cs
let be languages. prove that one of the following languages is a subset of the other and that they arent equal (give an example in which they differ).
intuitively, is the kleene closure of a language with a wider dictionary that contains all of the words of each of the languages or , so it would contain all the strings that those languages contain and strings of words combined from both languages that those languages cannot construct by themselves, this is an informal argument, we write a proof that using element chasing:
let , [[blk:eq-automata-homework1-2]] implies that or , in either case, each word is also in . by substituting and in [[blk:eq-automata-homework1-1]], we get that , the substitution is possible because and whether or (for all ) doesnt matter because in both cases because both are subsets of , since satisfies the membership condition of the set builder in [[blk:eq-automata-homework1-1]] it must be an element of .
a counter example for the equivalence would be . this implies that .
prove/disprove
the idea here is that for a string to be in the expression , it has to be in both sets and , on the other hand, for a string to be in the expression the "first part" of the string has to be in and the second part has to be a member of because we have the concatenation operation which draws "substrings" from the concatenated languages to create new strings. this suggests that if we should try constructing the languages such that contains a string whose first part and second part we should have , but to get a proper counter example we need to ensure that or by having that the substring cannot be found either of the languages and , or that the substring cannot be found in either of the languages . the following counter example resembles such a construction:
this gives us
as desired, we have the string with is in the expression on the left-hand side, but its parts arent found in the concatenated languages on the right-hand side, so that .
the intuition behind the incorrectness is that given the word , reversing to would make the first symbol of the last one in the word, and when reversing the whole thing that symbol becomes the first in , this doesnt "reverse the reversal", so it doesnt give us back.
counter example:
to prove , let , consequently, and:
to conclude the element chasing argument we note that:
a counter example for the inclusion of the opposite direction is , this way .
build a deterministic finite automaton that receives the language :
should tell us something about the variables . the operation can only give us one of the results , so we only accept sequence whose length modded by 3 gives us 2, formally this means that where . some examples are .
line of thoughts:
  1. it seems that we may need to differentiate between the state in which the automaton is seeing 's and between the state in which the automaton is seeing 's, because if the automaton detects a followed by an it shouldnt accept, so we may need a "dead" non-accepting state in which the computation may "die" and not proceed any further.
  2. we want to know at each state what the current length of the sequence modded by 3 would equal, this may be done by introducing 3 states for which the first would represent a result of 0, the second a result of 1, and the third a result of 2, this is because the only possible results are . however, it appears that we may need to have such 3 states for two different stages of the computation, the first is the stage of detecting 's, and the second is the stage of detecting 's, for the reason stated above.
with this in mind, we construct the automaton shown in fig-automata-homework1-1.
using a "product construction", build an automaton that receives the following language over : all the words that include and (note: the word must be accepted).
first we propose the automatons for each string, and then use their intersection. to detect we have fig-automata-homework1-2, to detect we have fig-automata-homework1-3.
using the product construction of fig-automata-homework1-2 and fig-automata-homework1-3, we get the final automaton fig-automata-homework1-4.
but a product construction could have some redundant states and transitions, for example, if you consider the state in fig-automata-homework1-4, it is unreachable from the initial state . fig-automata-homework1-5 gives the same automaton with some redundant states trimmed off.
let be the language of all the words over of which the first symbol is similar to the second to last one. (note: all possible words of length 2 are in the language). draw a nondeterministic finite automaton that accepts this language.
this can be done by applying the union construction to 2 DFAs where the first, , shown in fig-automata-homework2-1, recognizes words starting with the symbol and whose second-to-last symbol is also , and the second, , recognizes words starting with the symbol and whose second-to-last symbol is also .
is almost identical to because it recognizes the same pattern where the symbols have inverted roles. both automatons can be unionized to construct a DFA that recognizes both patterns. this is shown in fig-automata-homework2-2.
however, this can be done in a much simpler way if we introduce nondeterminism into our automata, we could simply turn fig-automata-homework2-1 into fig-automata-homework2-3. then, just as we did with fig-automata-homework2-2, we could use two similar automata and join them to get fig-automata-homework2-4.
let be a regular language, we define the following language:
meaning that for each word in we duplicate all its letters to receive a word in , prove that is also a regular language.
the idea is to start with an DFA that recognizes , and replace each transition labeled with some by a path of length 2 both of whose edges are labeled :
we have and so is a regular language by definition (because some finite automaton recognizes it).
let be languages over , we define :
prove that if and are regular languages then is aswell. note: the notation denotes the number of times the symbol appears in the word .
the idea is to use the product construction (to pass the sequence into 2 automatons simultaneously) and to simply ignore all transitions where the symbol is anything but 1, this can be done by turning transitions with the symbol 0 into empty transitions. this way, the product construction would only accept if both modified automatons accept, in which case the transitions with symbol 1 we'd have passed through would be equivalent in both modified automatons. let be a DFA (or NFA) that accepts and be a DFA (or NFA) accepting , we construct which accepts :
and are the modified versions of and , respectively. notice that we have that accepts the language
which is equivalent to .
in each of the following problems, prove that if is a regular language then the language received by the defined operation is also a regular language.
the idea is to modify the automaton that recognizes to allow it to skip any prefix and any suffix . to allow our automaton to skip any subsequence , a solution that comes to mind would be turning every state into an accepting state, but if we do this we may be allowing the automaton to take advantage of this to arbitrarily skip symbols while constructing . a better solution would be to introduce a new custom initial state that provides an empty transition to every state in the automaton, this new initial state would also be an accepting state but since nothing connects back to it, it cannot be reused. to allow our automaton to skip a suffix we turn every reachable state into an accepting state. to that end, let be an automaton such that , our new automaton that accepts would be defined as:
this new automaton recognizes and so its a regular language by definition.
the idea is to take a DFA that recognizes , replace each transition with two transitions of symbol and a state, this way we would be turning each symbol in into the two-symbol string , and we'll have covered . let such that , the automaton described is defined below:
this basically means that we're replacing the symbol of every transition with a symbol from some state to some state with two transitions with the symbol . the automaton recognizes . because we constructed an automaton that recognizes we know its a regular language.
we use states with an extra number 1 or 0 to indiciate whether we've skipped or not, we add empty transitions from states that have the "variable" equal to 0 to a new state, and link back with an empty transition to every state from the new state, this way we could allow the automaton to skip a single symbol . let , notice that to avoid accepting a we only let states where the indicator is 1 to be accepting states. the automaton is defined as:
we have hence is a regular language.
the solution is similar to the one for the previous problem, except that we use one extra state and and allow the automaton to loop on it to cover any possible sequence .
we have hence is a regular language.
first instinct would be to place an empty transition from the initial state to other states to skip a symbol, but this wouldnt work because it would allow the initial state to be used multiple times to skip symbols if some other state circles back to it. so just like in the previous problems, we adopt an indicator saying whether we've already skipped or not, turns out that in this case the indicator is only needed for the initial state to say whether this is our first time entering it, so its the only state that gets "duplicated" when constructing the new automaton. we can also drop the "indicator" and simply duplicate the state as the state itself can indicate whether its the "original" initial state or not, if its not, then it may transition to other states but is never entered more than once at the start. this is done by defining the following automaton:
we have hence is a regular language.
we add a new state, make it an accepting state, place empty transitions from every state that directs to an accepting state, then disable all other accepting states except the new one. this way we'll allow the automaton to traverse any path and skip any . let such that , then:
we have hence is a regular language too.
write the (simplest?) possible regular expressions that define each of the following languages over
  1. the language of words that end with an even number of 's or with an odd number of 's.
  2. the language of words in which the number of 's is not bigger than 2.
  3. the language of words in which the string appears exactly once.
  4. the language of words in which the number of 's is divisible by 2 but not by 3.
in relation to (4), that happens when the number of 's isnt a multiple of 6, so that the number of 's modulo 6 is 4 or 2, so we look for patterns of 6 's succeeded by 4 or 2.
  1. build a dfa with 4 states that recognizes the language defined by the expression
  2. build a finite automaton with 4 states that recognizes the language defined by
for (1):
for (2), we have
the automaton would be:
some states dont handle specific symbols to let the computation path die (this is a nondeterministic automaton).
which of the following equivalences are correct? explain or find a counter example
  1. .
  2. .
  3. .
  4. .
  1. correct, in both expressions every would be followed by a except the last one (same phrasing also holds for the case where the string is simply as the last , which is the only in this case, isnt followed by a .)
  2. the former contains words that only end with , but the latter can have words that end with , they're not equivalent.
  3. the latter can construct all words with any number of 's, and so can the former, they dont include anywhere, so they're equal. for the former, this is because , and denotes all words with an even number of 's, while simply denotes the language , so to any even number of 's we can add one to get any odd number of 's, thus giving us any sequence of 's of odd length or even length.
  4. both expressions construct the language defined by (atleast one followed by any number of 's followed by a ), they're equivalent.
prove/disprove: if is a regular language, is regular too.
regular languages are closed under complementation and intersection, so its a matter of constructing an automaton or a regex that recognizes words with a length modded by 3 resulting in 2 and using the product construction. the regex for the second automaton would be .
let be the language defined by , build a finite automaton that recognizes .
for every language over the alphabet we define the operation
let , find .
is essentially the set of all words from that dont have a suffixed "clone" in . the set of strings that arent prefixes in other strings in are ones in which , such as , because of the restriction . a suffixed string starting with one of these strings would violate that restriction. hence
let , find .
to every string in we can freely add as many 's as we want, so .
prove/disprove: if is regular then .
the statement is false, consider the simple counter example which is the language recognized by the regular expression , we have .
if is regular then is regular.
notice that we have , hence:
is a regular language because regular language are closed under concatenation, complementation and intersection.
let , we define to be the word received by separating the 's from 's, i.e. the writing of all occurrences of and then those of . e.g. . let . we define .
if , what is ?
prove/disprove: if is a regular language then so is .
isnt necessarily a regular language because we know isnt regular by the [[blk:exa-pumping-lemma-1]].
prove/disprove: if isnt a regular language then isnt.
this isnt necessarily true, consider the language , we have which is a regular language because constructing an automaton that recognizes an even number of 's followed by a is trivial.
given defined by
prove that isnt regular.
assume in contradiction that is regular, let be the pumping length provided by the pumping lemma, for every string , since , has to be all 's but if we consider the result we see that pumping isnt possible, which gives us the necessary contradiction and so the language isnt regular.
prove that is nonregular.
i was challenging my understanding when i wrote this solution, trying to get a better grasp of the method.
it seems that by picking a string like we can pump it however we want with 0's and it would still be in the language because it wouldnt break the rule . but that isnt true, atleast not for all possible values of , if we pick all the exponents to be equal i.e. , and pick to be their length, i.e. , we would be restricting the "pumping string" to only 0's (like in [[blk:exa-pumping-lemma-2]]), and breaking the restriction first so that when we try to pump the string with 0's we would break the second restriction, , hence showing that the pumping lemma isnt satisfied by contradiction, and so the language is nonregular.
prove that is nonregular.
as usual, a proof by contradiction, assume is regular so that the pumping lemma holds, let be the pumping length provided by the pumping lemma, consider the string of length , this string cannot be pumped, because any string of length where isnt in because the next longest string after that of length is gonna be of length , and is smaller than for . so must be nonregular because assuming it is causes a contradiction.
use the pumping lemma to show that the language is not context free.
we assume that is a CFL and obtain a contradiction. let be the pumping length for that is guaranteed to exist by the pumping lemma. select the string . clearly is a member of and of length at least . the pumping lemma states that can be pumped, but we show that it cannot. in other words, we show that no matter how we divide into , one of the three conditions of the lemma is violated. first, condition 2 stipulates that either or is nonempty. then we consider one of two cases, depending on whether substrings and contain more than one type of alphabet symbol.
  1. when both and contain only one type of alphabet symbol, does not contain both ’s and ’s or both ’s and ’s, and the same holds for . in this case, the string cannot contain equal numbers of 's, 's, and 's. therefore, it cannot be a member of . that violates condition 1 of the lemma and is thus a contradiction.
  2. when either or contains more than one type of symbol, may contain equal numbers of the three alphabet symbols but not in the correct order. hence it cannot be a member of and a contradiction occurs.
one of these cases must occur. because both cases result in a contradiction, a contradiction is unavoidable. so the assumption that is a CFL must be false.
thus we have proved that B is not a CFL.
[cite:;from @sipser_comp_2012 example 2.36]
let . use the pumping lemma to show that is not a cfl. assume that is a cfl and obtain a contradiction. let be the pumping length given by the pumping lemma.
this time choosing string is less obvious. one possibility is the string . it is a member of and has length greater than , so it appears to be a good candidate. but this string can be pumped by dividing it as follows, so it is not adequate for our purposes.
let's try another candidate for . intuitively, the string seems to capture more of the "essence" of the language than the previous candidate did. in fact, we can show that this string does work, as follows.
we show that the string cannot be pumped. this time we use condition 3 of the pumping lemma to restrict the way that can be divided. it says that we can pump by dividing , where .
first, we show that the substring must straddle the midpoint of . otherwise, if the substring occurs only in the first half of , pumping up to moves a 1 into the first position of the second half, and so it cannot be of the form . similarly, if occurs in the second half of , pumping up to moves a 0 into the last position of the first half, and so it cannot be of the form .
but if the substring straddles the midpoint of , when we try to pump down to it has the form , where and cannot both be . this string is not of the form . thus cannot be pumped, and is not a CFL.
[cite:;taken from @sipser_comp_2012 example 1.75]
where is , defined by
in the ladder of language hierarchy?
does pertain the pumping property, but it isnt regular, try to find equivalence relations.
it is recognized by the following grammar:
isnt regular, doesnt pertain the pumping lemma
recognized by cfg
recognized by
pertains the pumping lemma, but isnt regular (prove it)
if we consider where is the pumping length provided by the pumping lemma, and then consider the cases where 1. we try to pump with a string of 's and 's on the left side, we'd notice that we'd get a string that isnt formed of the proper lumps of the form , 2. we try to pump on the left side before with a string of 's, we wouldnt be able to have any 's to pump with on the right side to keep lengths equal, because of the third condition of the pumping lemma, , here we have as , so cannot contain any symbols, 3. try to pump with only 's, we'd be violating the condition after pumping repeatedly. this way we'd be showing that each case leads to a contradiction.