Interview Questions.

Question 1. What Is The Difference Between The Strings And The Words Of A Language?

Answer :

A string is any mixture of the letters of an alphabet wherein because the words of a language are the strings which can be constantly made according to sure regulations used to outline that language.For example if we take

Alphabet Σ =  a , b   Here a , b are the letters of this alphabet.

As you can see we will make a variety of strings from those letters a and b.

For instance a,b,aa,ab,ba,bb,aaa,aab,aba,baa,…………………… and so on.

But when we outline a language over this alphabet having no a’s and handiest unusual variety ofb’s. Then the phrases of this language would have handiest those strings that have best atypical quantity of b’s and no a’s.A few example phrases of our defined language are b , bbb , bbbbb , bbbbbbb ,……………………………..And so on.

So we are able to say that each one the words are strings however all the strings may not be the words of a language. Hence strings are any aggregate of letters of an alphabet and the phrases of a language are strings made in step with a few rule.

Question 2. What Is The Difference Between An Alphabet And An Element Of A Set. Whether Alphabet Is An Element Of A Set Or It Is A Set Itself?

Answer :

An Alphabet is a hard and fast in itself. The factors of an Alphabet are known as letters.

For example

Binary Alphabet Σ = 0,1

Here zero,1 are the letters of binary alphabet.

Binary Alphabet may be very essential as it the Alphabet used by the laptop.

Set of Natural Numbers

N=1,2,3,four,5,…………………………………..

Here 1,2,three……………………………………. Are the elements of set of Natural Numbers.

Computer Science Engineering Interview Questions
Question three. What Is Null String (Λ) ?

Answer :

The string with 0 occurrences of symbols (letters) from ∑.

It is denoted by (Small Greek letter Lambda) λ or (Capital Greek letter Lambda) Λ, is referred to as an empty string or null string.

The capital lambda will in most cases be used to indicate the empty string, in further discussion.

Question four. What Is The Concept Of Valid And Invalid Alphabets ?

Answer :

While defining an alphabet of letters inclusive of multiple symbols, no letter must be started out with any other the letter of the identical alphabet i.E. One letter should no longer be the prefix of another. However, a letter can be ended inside the letter of same alphabet i.E. One letter may be the suffix of any other.

Σ=  a , b  ( Valid Alphabet)
Σ=  a , b , cd  ( Valid Alphabet)
Σ=  a , b , ac  ( Invalid Alphabet)

AWT (Abstract Window Toolkit) Tutorial
Question five. What Is Algol ?

Answer :

ALGOL (ALGOrithmic Language) is one of several excessive stage languages designed specifically for programming scientific computations. It commenced out inside the late 1950’s, first formalized in a document titled ALGOL 58, and then improved through reports ALGOL 60, and ALGOL sixty eight. It turned into designed through an worldwide committee to be a popular language. Their authentic conference, which befell in Zurich, became one of the first formal tries to cope with the difficulty of software program portability. ALGOL’s system independence authorized the designers to be more creative, but it made implementation tons greater hard. Although ALGOL by no means reached the level of industrial recognition of FORTRAN and COBOL, it's far taken into consideration the most crucial language of its technology in terms of its have an impact on on later language improvement.

ALGOL’s lexical and syntactic structures became so famous that really all languages designed on the grounds that had been referred to as “ALGOL – like”; that is they had been hierarchical in shape with nesting of each environments and manipulate systems.

AWT (Abstract Window Toolkit) Interview Questions
Question 6. What Is Non-determinism And Determinism And What Is The Difference Between Them ?

Answer :

Determinism means that our computational model (device) knows what to do for each possible inputs. Non determinism our device may or won't know what it has to do on all possible inputs.

As you may finish from above definition that Non-Deterministic device cannot be applied ( used ) on laptop unless it is converted in Deterministic system.

Question 7. What Is Meant By Equivalent Fa’s ?

Answer :

FA’s that take delivery of the equal set of languages are known as Equivalent FA’s.

Question eight. What Is The Difference Between Palindrome And Reverse Function?

Answer :

It is to be denoted that the phrases of PALINDROME are known as palindromes.

Reverse   = w

Example: Σ=a,b,

PALINDROME=Λ , a, b, aa, bb, aaa, aba, bab, bbb, …

If a is a phrase in some language L, then reverse (a) is the same string of letters spelled backwards, known as the opposite of a.

E.G

reverse (xxx) = xxx
opposite (623) = 326
reverse (a hundred and forty) = 041

Question 9. Valid/in-legitimate Alphabets?

Answer :

Any alphabet is valid if any of its letter does now not appear inside the begin of any other letter in any other case it's far invalid.

Question 10. What Is Reverse Of A String?

Answer :

Alphabet provides best a fixed of symbols. A string is a concatenation of those symbols. Reverse of the string means to write down the string in reverse order. It has no impact on alphabet. Alphabet will remain identical.

Question eleven. Differentiate Kleene Star Closure And Plus?

Answer :

Given Σ, then the Kleene Star Closure of the alphabet Σ, denoted by using Σ*, is the gathering of all strings described over Σ, together with Λ.

Plus Operation is equal as Kleene Star Closure besides that it does no longer generate Λ (null string), automatically.

Given Σ, then the Kleene Star Closure of the alphabet Σ, denoted with the aid of Σ*, is the collection of all strings defined over Σ, together with Λ.

Plus Operation is equal as Kleene Star Closure except that it does not generate Λ (null string), robotically.

You can use different image for alphabet however we are by and large use sigma image.

Question 12. Define Regular Expression?

Answer :

Regular Expression is the generalized form of any everyday language through which you may construct any string related to that language.

Take an example from your handouts

L1 = Λ, a, aa, aaa, … and L2 = a, aa, aaa, aaaa, … can absolutely be expressed by a* and a+, respectively.

So a* and a+ are the generalized form of Languages L1, L2.

And a* and a+ are known as the normal expressions (RE) for L1 and L2 respectively.

Computer Science Engineering Interview Questions
Question thirteen. What Is The Concept Of Fa Also Known As Fsm ( Finite State Machine) ?

Answer :

FA (Finite Automaton) is a finite state system that recognizes a normal language. In computer science, a finite-state device (FSM) or finite-kingdom automaton (FSA) is an summary machine that has most effective a finite, constant quantity of reminiscence. The inner states of the machine deliver no similarly structure. This sort of model may be very extensively used inside the look at of computation and languages.

Question 14. What Is The Difference Between Fa , Tg , Gtg. ?

Answer :

In each FA, we mark transitions with single letter of the given alphabet however in TG transitions may be marked with letters or strings (aggregate of letters).

In each FA, each nation indicates transition for all letters of given alphabet however in any TG it isn't necessary to expose all transition for all letters of given alphabet. In TG, we may or won't show all letter transitions according to requirement. We also can show transitions on analyzing any strings in TGs however it isn't always feasible in FA’s. In GTG Directed edges connecting some pair of states are categorised with ordinary expressions . It can be referred to that in GTG, the labels of transition edges are corresponding ordinary expressions. In TG we write strings and in GTG we're bound to write down RE. Every FA is likewise a TG however now not each TG is FA.

Question 15. What Is The Difference Between Fa’s And Tg’s .Why We Need Tg’s When We Have Fa’s?

Answer :

The Transition Graphs (TG) vary from FA inside the following areas

TG’s are generalizations of FA’s.
TG’s can exchange nation without an input ( Null transition).
Can study more than one letter (words of the language they're accepting) alongside the transition edges at a time.
Can have a normal expression as a side label.
Can have more then one begin kingdom.
We have been given greater freedom in TG’s. But this freedom is on the cost of more memory and processing strength it manner that if we enforce TG’s on computer the usage of a few programming language it will want more reminiscence and processing electricity of pc than used in the implementation of FA’s.

Question sixteen. What Is The Concept Of The Union Of Fa’s ?

Answer :

When we take Union of  FA’s it means that resultant FA’s must receive all the words that have been established by the two FA’s personally. It is like taking union of two sets, the consequent set contain individuals of each units.

For example

Let A =1,3,5,7,nine
and
B = 0,2,four,6,8,10
then, A U B =  0,1,2,three,four,five,6,7,eight,9,10 

you could see that A U B comprise elements of both units similar is the case with FA’s.

Question 17. What Is The Difference Between Is Tg And Gtg ?

Answer :

In TG, there are letter transitions for the strings. While in GTG, you could write whole RE as a transition from one country to some other one.

Question 18. What Is Difference Between Fa’s And Nfa’s. Are They Opposite To Each Other ?

Answer :

FA stands for finite automata while NFA stands for non-deterministic finite automata, In FA there have to be a transition for each letter of the alphabet from each country. So in FA variety of transitions should be same to (number of states * variety of letter in alphabet).

While in NFA there may be more than one transition for a letter from a kingdom. And finally each FA is an NFA even as every NFA can be an FA or no longer.

AWT (Abstract Window Toolkit) Interview Questions
Question 19. Differentiate Between (a,b) And (a+b)?

Answer :

(a, b) = Represents a and b.

(a + b) = Represents either a or b.

Question 20. What Is The Difference Between Gt And Gtg ?

Answer :

In TG, there are transitions for the strings. While in GTG, you can write complete RE as a transition from one state to any other one.

Question 21. How To Create A Re Of A Particular Language?

Answer :

Regular expression is used to explicit the endless or finite language, those RE are made in this kind of way that these can generate the strings of that unique language additionally for the go take a look at that the described RE is of a particular language that RE need to be given all the string of that language and all language strings ought to be time-honored by means of that RE.

Question 22. How Diagrams Of Fa’s Are Created ?

Answer :

It depends upon the question what number of states contain in a FA. There is not any formal manner to design FA for a language. This ability simply improves with time and exercise.

Every FA is also a TG however not every TG is FA. In every FA, every state shows transition of all letters of given alphabet however in any TG it is not have to. In TG, we may also or might not show all letters transition according to requirement. We also can show transitions on analyzing any strings in TGs but it isn't feasible in FAs.

Question 23. What Is The Difference Between Fa’s ,and Tg’s ?

Answer :

There are two or 3 massive differences between FA’s and TG’s.

In FA there can be maximum one initial or beginning state while in TG there can be more than one initial kingdom.

In FA there can be transition for letters simplest even as in TG transitions from a nation to some other one can be for strings.

In FA there should be transition from every nation for each letter (deterministic) whilst in TG there can be no transition for specific letter from a state and there may be more than one route for a string or letter from a kingdom.

Question 24. What Is The Exact Definition Of Fa ?

Answer :

Definition: A Finite automaton (FA), is a collection of the followings

Finite wide variety of states, having one initial and some (perhaps none) very last states.
Finite set of enter letters (Ó) from which enter strings are formed.
Finite set of transitions i.E. For every state and for every input letter there's a transition displaying how to move from one country to any other.
Question 25. What Is The Concept Of Nondeterministic Finite Automaton (nfa) ?

Answer :

Nondeterminism performs a key function within the principle of computing. A nondeterministic finite state automaton is one wherein the current state of the machine and the contemporary input do no longer uniquely determine the following country. This simply way that a number of next states (0 or more) are viable next states of the automaton at every step of a computation. Of course, nondeterminism is not practical, due to the fact in real life, computers must be deterministic. Still, we can simulate nondeterminism with deterministic packages. Furthermore, as a mathematical device for expertise computability, nondeterminism is worthwhile.

As with deterministic finite nation automata, a nondeterministic finite country automaton has five components.

A hard and fast of states
a finite input alphabet from which enter strings can be built
a transition feature that describes how the automaton changes states as it processes an input string
a unmarried targeted beginning nation
a hard and fast of accepting states
The most effective distinction lies within the transition function, that may now target subsets of the states of the automaton in place of a single subsequent nation for every kingdom, enter pair.

Question 26. If A Language Can Be Expressed In The Form Of Fa Than Why It Is Needed To Use Nfa ?

Answer :

NFA stands for non-deterministic FA and this type of structure has rest as compared with FA. So it's miles as a substitute extra easy to represent a language the usage of NFA.

We have techniques to transform NFA into FA’s so on occasion it's miles less difficult to construct NFA of a given language and than convert its NFA into FA the usage of these techniques as opposed to immediately constructing an FA for a language which may be very hard.

Question 27. How To Made Nfa Corresponding To The Closure Of An Fa ?

Answer :

While producing NFA similar to closure of an FA one must take care of the null string. Simple way to simply accept null string is claim preliminary nation, final as nicely. But on this way lots of other strings may also be accepted.

Therefore, accurate manner is draw every other country. Declare the brand new kingdom preliminary in addition to final. Connect the brand new state with the states at the beginning related with the vintage begin country with the identical transitions as the old start kingdom. Newly drawn diagram will be an NFA representing the language closure of the given FA

Question 28. How Moore And Mealy Machine Works In Computer Memory What Is Their Importance In Computing ?

Answer :

Mealy & Moore Machines paintings in computing as incrementing system & 1’s complement system and so on. These operations as simple laptop operations so these machines are very important.

Question 29. What Is The Significance Of Pumping Lemma Ii ?

Answer :

The significance of 2nd model of ‘pumping lemma’ is that there are a few endless non regular languages like PALINDROME we can constructed FA which can receive there positive phrases but if we growth the period in their phrases that FA don’t take delivery of those words so by means of pumping lemma version I it's miles very difficult to show them non everyday but with the second one model we will show that a language is Non ordinary even it’s some words can be everyday with the aid of a few FA’s.

Question 30. Moore And Mealy Machine?

Answer :

In order to run a string on a Mealy or Moore gadget, you could take guidelines from transition desk. Running string on Mealy or Moore system is just like jogging string on a FA. For example, if need to run abba on the gadget, take begin from initial country. Check what's the transition for a, what country it is going. After that take a look at what's the path of b from that nation and so on. In this manner you will be able to run whole of the string. Note that there is no very last country in Mealy or Moore device. So there's no case of attractiveness or rejection of string. You simply have to decide what the output is. I wish in an effort to clear your mind for similarly clarification please listens in your lecture carefully.
The string is taken for the testing purposes. You can take any form of string and decide its output the usage of gadget.
Question 31. What Is The Difference Between Semiword And Word Please Also Give An Example Regarding This?

Answer :

Word: A phrase is entire combos of terminals only e.G. Abba or ab or a or null string.

Semiword: A semiword is a string of terminals (may be none) concatenated with precisely one nonterminal at the right i.E. A semi phrase, in popular, is of the subsequent form (terminal)(terminal) ——- (terminal)(nonterminal)

For instance

aaaaaaB , aabbaaaA , A.

Question 32. What Is The Difference Between Derivation Tree And Total Tree ?

Answer :

A Derivation tree is the only that indicates the way to derive any unique phrase of the language described by means of CFG however Total Language Tree indicates all phrases of the Language defined through CFG on it.

Question 33. What Does Mean The Language Is Closed?

Answer :

When we are saying that a Language is closed it's miles continually with recognize to certain operation.

A easy example can be that the set of integers is closed below addition. It way when we take two numbers from set of integers say 3, 7 the end result of their addition would also be within the set of integers.

Similarly if the result of an operation at the words of a language effects within the word of the same language we say that the language is closed underneath that operation.

Question 34. What Are The Productions?

Answer :

Productions are the grammatical guidelines and rules. These guidelines explicit the behavior of CFG. Using production in CFG terminals are converted into non-terminals and while all of the terminals are transformed the use of productions, a word is acquired.

Question 35. What Is The Difference Between Concatenation And Intersection Of Two Fa’s Also What Is The Difference Among Union Of Two Fa’s And Addition Of Them?

Answer :

In intersection of  FA’s most effective those strings are normal which can be independently popular by each FA’s, while in concatenation of  FA’s most effective the ones strings may be regular in which first a part of string is general by using first FA and final part of string is established by means of the second FA.

While taking union of two FA’s you'll be able to constitute it the use of + signal. So (FA1 U FA2) and (FA + FA2) each are equal. There isn't any difference between them.

Question 36. Is It Possible To Make Cfg For Infix And Post-repair Expression’s Using Derivation Tree ?

Answer :

Derivation tree is best used to derive phrases of language that is defined by way of a CFG. Yes, we will create CFG for languages infix expressions, postfix expressions.

Question 37. What Is The Uses Of Push Down Automata In Computing ?

Answer :

PDA is simply an enhancement in FAs. I.E Memory is attached with device that recognizes some language. FA is fundamental structure for most advanced digital machines inclusive of laptop etc.

Question 38. What Is Difference Between Push Down Stack And Push Down Store ?

Answer :

No distinction at all. Both terms are used to describe reminiscence shape connected with FAs to save a few characters in it.

Question 39. What Is Meant By The Terms Stack Consistence And Input Tape Consistence ?

Answer :

Term Stack constant means we will pop any individual from the top of the stack most effective. PDA need to now not be able to pop any character apart from this is present on the top of the stack.

Term Tape regular method we will study simplest the first letter at the tape not every other letter of the tape after the primary one.

Question forty. What Is Unit Production?

Answer :

The manufacturing in which one non-terminal ends in most effective one non-terminal.