VU Students Online Learning Community

A method of generating strings from a CFG starting from the leftmost symbol

One non-terminal leads to only one non-terminal

Unwanted branches do not lead to the required word

<p>Intersection includes words present in both languages, while union includes words from at least one language</p> Signup and view all the answers

<p>Concatenation of finite letters from an alphabet</p> Signup and view all the answers

<p>A string with no symbols, denoted by Lambda, that represents an empty sequence</p> Signup and view all the answers

<p>A word follows language rules, whereas a string is a finite sequence of symbols</p> Signup and view all the answers

<p>The collection of all strings over an alphabet, including the empty string and all concatenations of the alphabet</p> Signup and view all the answers

<p>Because the palindrome definition requires that the reverse of a string equals itself</p> Signup and view all the answers

<p>Specify basic objects, define initial objects if necessary, define each object in terms of other objects</p> Signup and view all the answers

<p>aaa + aab + aba + abb + baa + bab + bba + bbb</p> Signup and view all the answers

<p>((a+b)(a+b))*</p> Signup and view all the answers

<p>(a + b)*</p> Signup and view all the answers

<p>TG's can change state without an input (Null transition), providing more freedom but needing more memory and processing power.</p> Signup and view all the answers

<p>A Finite automaton is a collection of finite number of states, with one initial and possibly some final states, a finite set of input letters, and transitions for each state and input letter showing how to move between states.</p> Signup and view all the answers

<p>FA transitions are deterministic with one transition per letter per state, while NFA's transitions can have more than one transition per letter per state.</p> Signup and view all the answers

<p>In NFA, the next state of the machine and current input do not uniquely determine the next state, allowing for multiple possible subsequent states.</p> Signup and view all the answers

<p>NFA provides a more relaxed structure and it is easier to represent a language using NFA, allowing for the use of methods to convert NFA into FA to simplify representation.</p> Signup and view all the answers

<p>Introduce a new state connected to the original start state with the same transitions, designating the new state as initial and final to accurately accept the null string.</p> Signup and view all the answers

<p>The union of two FA's accepts strings accepted by either FA, concatenation accepts strings where the first part is accepted by the first FA and the second part by the second FA, and closure accepts all strings of the first FA including the empty string.</p> Signup and view all the answers

<p>Moore &amp; Mealy Machines work as incrementing machine &amp; 1's complement machine in computing, providing basic computer operations.</p> Signup and view all the answers

<p>A sequential circuit contains a memory component that provides a state input, often using flip-flops to indicate states and transitions based on inputs.</p> Signup and view all the answers

<p>Pumping Lemma I and II are used to recognize non-regular languages, with PLII having stricter conditions than PLI. PLI requires generating all words of a language to prove non-regularity, while PLII needs only a single word.</p> Signup and view all the answers

<p>Pumping Lemma II is significant as it can prove certain infinite non-regular languages, like PALINDROME, non-regular by easily showing the non-acceptance of certain words.</p> Signup and view all the answers

<p>A word consists of complete combinations of terminals, while a semiword includes terminals concatenated with exactly one nonterminal on the right.</p> Signup and view all the answers

<p>Grammatical rules and regulations</p> Signup and view all the answers

<p>Intersection accepts strings accepted by both FA's independently, while concatenation accepts strings where the first part is accepted by the first FA and the remaining part by the second FA.</p> Signup and view all the answers

<p>There is no difference between the union of two FA's (FA1 U FA2) and the addition of them (FA + FA2), as both operations represent the combination of the languages of the FA's.</p> Signup and view all the answers

<p>All strings ending in 'a'</p> Signup and view all the answers

<p>The first phase of the compiler that recognizes basic language units called tokens</p> Signup and view all the answers

<p>Strings that follow the rules of the language</p> Signup and view all the answers

<p>A tabular representation of a function that takes two arguments and returns a value</p> Signup and view all the answers

<p>Transfer of a letter from one state to another after being read</p> Signup and view all the answers

<p>A string having no letter</p> Signup and view all the answers

<p>(r - 1)'s complement of a number N in base r is rn - r - m - N</p> Signup and view all the answers

<p>A component that holds input for some time and forwards it</p> Signup and view all the answers

<p>Languages determined by regular expressions are regular; otherwise, they are non-regular</p> Signup and view all the answers

<p>A nondeterministic finite state automaton where the next state is not uniquely determined by current state and input</p> Signup and view all the answers

<p>NFA allows various moves and multiple next states; FA has unique transitions with no choices</p> Signup and view all the answers

<p>A string is any combination of the letters of an alphabet whereas the words of a language are the strings that are always made according to certain rules used to define that language.</p> Signup and view all the answers

<p>A word consists of only terminals, while a semiword contains a terminal concatenated with exactly one nonterminal on the right</p> Signup and view all the answers

<p>A derivation tree shows the derivation of a specific word of the language, while a total tree shows all words of the language</p> Signup and view all the answers

<p>An Alphabet is a set in itself. The elements of an Alphabet are called letters.</p> Signup and view all the answers

<p>The string with zero occurrences of symbols (letters) from an alphabet. It is denoted by (Small Greek letter Lambda) or (Capital Greek letter Lambda), is called an empty string or null string.</p> Signup and view all the answers

<p>Practice and familiarity with production rules help in removing ambiguity</p> Signup and view all the answers

<p>Null production produces empty string, while nullable production can lead to empty string through derivation; To handle, delete null productions and add appropriate new productions</p> Signup and view all the answers

<p>The language consisting of (Null String) and the strings s defined over an Alphabet such that Rev(s)=s.</p> Signup and view all the answers

<p>Valid alphabets consist of more than one symbol where no letter is the prefix of another letter of the same alphabet. Invalid alphabets have letters that start with or end in other letters of the same alphabet.</p> Signup and view all the answers

<p>The Pumping Lemma is a theorem to verify the regularity of infinite languages; It ensures that regular languages exhibit loops</p> Signup and view all the answers

<p>ALGOL (ALGOrithmic Language) is one of several high-level languages designed specifically for programming scientific computations.</p> Signup and view all the answers

<p>Sequencing operators are operators that match elements in sequence, such as 'a &gt;&gt; b', 'a &amp;&amp; b', and 'a || b'.</p> Signup and view all the answers

<p>Determinism means that a machine knows what to do for every possible input, while Non-Determinism means the machine may or may not know what to do on all possible inputs.</p> Signup and view all the answers

<p>FA's that accept the same set of languages are called Equivalent FA's.</p> Signup and view all the answers

<p>Palindromes are words of a language where the reverse function returns the same string. Reverse function simply reverses a string.</p> Signup and view all the answers

<p>Given an Alphabet, the Kleene Star Closure, denoted by *, is the collection of all strings defined over the alphabet, including the empty string.</p> Signup and view all the answers

<p>Any alphabet is valid if none of its letters appear at the start of any other letter. Otherwise, it is invalid.</p> Signup and view all the answers

<p>The reverse of a string means to write the string in reverse order. This operation does not change the alphabet.</p> Signup and view all the answers

<p>Kleene Star Closure includes the empty string, while PLUS operation does not generate the empty string automatically.</p> Signup and view all the answers

<p>Regular Expression is the generalized form of any regular language through which you can construct any string related to that language.</p> Signup and view all the answers

<p>FA (Finite Automaton) is a finite state machine that recognizes a regular language.</p> Signup and view all the answers

<p>Taking the union of two FA's means the resulting FA should accept all the words accepted by the two FA's individually.</p> Signup and view all the answers

<p>TG has letter transitions for the strings, while GTG has whole regular expressions as transitions between states.</p> Signup and view all the answers

<p>There is no fixed formula to generate Regular Expressions. It is based on the specific language and patterns.</p> Signup and view all the answers

<p>Yes, for both infix and postfix expressions</p> Signup and view all the answers

<p>PDA is an enhancement in FAs where memory is attached to the machine. It is used in advanced electronic machines such as computers.</p> Signup and view all the answers

<p>There is no difference. Both terms describe the memory structure attached with FAs to store characters.</p> Signup and view all the answers

<p>In CNF, if null is part of the language, it is not included. This is the main change a language undergoes in CNF. FAs are drawn without affecting the language when null is part of it.</p> Signup and view all the answers

<p>In CNF, null is not part of the language. The only change in CNF is excluding null. When building a PDA from CFG, the language remains the same as the original CFG.</p> Signup and view all the answers

<p>PDA consists of input letters, input tape, stack characters, a pushdown stack, start state, accept and reject states, push state, pop state, and read state.</p> Signup and view all the answers

<p>Automata theory helps in studying abstract computing devices and what is computable using an abstract machine. It is fundamental for creating compilers, programming languages, and analyzing new computing devices.</p> Signup and view all the answers

<p>Rules for forming words vary for different languages. Strings must adhere to the defined rules of the language. For example, even and odd length strings have different valid and invalid word patterns.</p> Signup and view all the answers

<p>Palindromes of even length are symmetric about the middle line, while palindromes of odd length are symmetric about the middle letter. Palindromes of length 2n and 2n-1 depend on the alphabet used.</p> Signup and view all the answers

<p>Regular expressions for a specific number of words can be written using the alphabet of the language. Example: (a+b)3 represents all possible strings with the length of 3, where 'a' and 'b' are the alphabet characters.</p> Signup and view all the answers

<p>Capital letters are used for convenience when representing languages. Yes, two languages can be combined by using operations like union, intersection, etc.</p> Signup and view all the answers

<p>Rules include defining languages for single letters, product of two languages, union of sets, and Kleene closure. These rules establish a language associated with each regular expression.</p> Signup and view all the answers

<p>Even-Even language refers to strings where the counts of 'a's and 'b's are both even. It can be divided into substrings of length 2 each.</p> Signup and view all the answers

<p>Tokenize a string means make its valid units.</p> Signup and view all the answers

<p>Whole star of any regular expression means all possible combinations of that regular expression, including empty string.</p> Signup and view all the answers

<p>Plus operation is similar to Kleene Star Closure, but it does not generate a null string automatically.</p> Signup and view all the answers

<p>Null string is used in FA if it is part of the language, but it is not compulsory to include.</p> Signup and view all the answers

<p>(a, b) represents the combination of a and b, while (a + b) represents either a or b</p> Signup and view all the answers

<p>(a + b)+ means repeat the expression one or more times, while (a + b)* means repeat the expression zero or more times</p> Signup and view all the answers

<p>The length of a string indicates the number of symbols in that string.</p> Signup and view all the answers

<p>False</p> Signup and view all the answers

<p>FA = Finite Automata with unique transitions TG = Generalization of FA with additional features GTG = Directed edges labeled with regular expressions</p> Signup and view all the answers

<p>Language of strings with substring 00 or 11 in them at least. Minimum words included in this language are 00 and 11. This language does not accept null, 0, or 1.</p> Signup and view all the answers

<p>Single 0's or 1's means words with either 0's or 1's without null. Double 0's or 1's means clumps of letters that will always come together.</p> Signup and view all the answers

<p>It depends on the expression given to us.</p> Signup and view all the answers

<p>There is not any formal procedure to know the number of states. This ability improves with time and practice.</p> Signup and view all the answers

<p>Transition means which letter, after being read, is transferred from which place to which place. It is necessary to show the transition of every letter from each state.</p> Signup and view all the answers

<p>No, if any state starts from the final state, it does not accept any string. It does not accept the null string either, as there is no path starting from the initial state and ending in the final state.</p> Signup and view all the answers

<p>A Finite Automaton (FA) should accept all words of the language and reject all words not part of the language. Any FA meeting these criteria is suitable for the language.</p> Signup and view all the answers

<p>The DEAD STATE is introduced to be able to make an automaton complete without altering its behavior.</p> Signup and view all the answers