undefined | unit 5 context free languages

ALC

Unit-5Context free languages Q1) Define Turing machine?A1) Turing machineA Turing Machine (TM) is a mathematical model which comprises of an infinite length tape divided into cells on which input is given. It has a head which reads the input tape. A state register stores the current state. After an input symbol is read, it is replaced by another symbol, its internal state gets changed, and it moves from one cell to the right or left. After reaching the final state, the input string is accepted, otherwise rejected.A TM can be formally described as a 7-tuple (Q, X, ∑, δ, q0, B, F) where −● Q is a finite set of states● X is the tape alphabet● ∑ is the input alphabet● δ is a transition function; δ : Q × X → Q × X × {Left shift, Right shift}.● q0 is the initial state● B is the blank symbol● F is the set of final statesExample Turing machine M = (Q, X, ∑, δ, q0, B, F) with● Q = {q0, q1, q2, qf}● X = {a, b}● ∑ = {1}● q0 = {q0}● B = blank symbol● F = {qf } δ is given by −

Tape alphabet symbol	Present State ‘q0’	Present State ‘q1’	Present State ‘q2’
a	1Rq1	1Lq0	1Lqf
b	1Lq2	1Rq1	1Rqf

Here 1Rq1 🡪 write symbol is 1, the tape moves right, and the next state is q1. Similarly, 1Lq2 🡪 write symbol is 1, the tape moves left, and the next state is q2. Q2) Write short notes on context free language?A2) Context free language (CFL) CFLs are used by the compiler in the parsing phase as they define the syntax of a programming language and are used in many editors.There are four important components in a grammatical description of a language:

There is a set of symbols that form the strings of the language being defined. They are called terminal symbols, represented by V t .

There is a finite set of variables, called non-terminals. These are represented by V n .

One of the variable represents the language being defined; it is called the start symbol. It is represented by S.

There are finite set of rules called productions that represent the recursive definition of a language. Each production consists of:

● A variable that is being defined by the production. This variable is often called the head of the production.● The production symbol ->.● A string of zero or more terminals and variable. Q3) write pumping lemma for CFL ?A3) Pumping lemmaLemma: The language L = {anbncn | n>=1} is not context free. Proof (By contradiction)Assuming that this language is context-free; hence it will have a context-freegrammar.Let K be the constant of the Pumping Lemma.Provided the aKbKcK series, where L is greater than K in duration. By the Pumping Lemma this is represented as uvxyz, such that all uvixyiz are also in, which is not possible, as: either v or y cannot contain many letters from {a,b,c} ; else they are in the wrong order .if v or y consists of ‘a’s, ‘b’s or ‘c’s, then uv2xy2z cannot maintain the balance amongst the three letters.Lemma: The language L = {aibjck | i < j and i < k} is not context free.Proof (By contradiction)Assuming that this language is context-free; hence it will have a context-free grammar.Let K be the Pumping Lemma constant.Considering the string aKbK+1cK+1, which is L > K.By the Pumping Lemma this must be represented as uvxyz, such that all uvixyiz are also in L.-As mentioned previously neither v nor y may contain a mixture of symbols.-Suppose consists of ‘a’s.Then there is no way y cannot have ‘b’s and ‘c’s. It generates enough letters to keepthem more than that of the ‘a’s (it can do it for one or the other of them, not both). Similarly, y cannot consist of just ‘a’s.So, suppose then that v or y contains only ‘b’s or only ‘c’s.Consider the uv0xy0z string that must be in L. Since both v and y have been dropped, we must have at least one 'b' or one 'c' less than we had in uvxyz, which It was akbk+1ck+1. Consequently, to be a member of L, this string no longer has enough of either 'b's or' c's. Q4) Write short notes on Non-context free language?A4) Non - context free language (Non - CFL)Not all languages are CFL. Non-CFL is the name of languages that are not Context-Free. The analysis of the word production machine from grammar is required to prove the point that all languages are not meaning - free. live production: A live production is called a production of the nonterminal form * strings of two non-terminals. dead production: A development of the non-terminal * terminal form is referred to as a dead production. It should be noted that all CFGs in the CNF only have these types of output. The theorem below is Theorem: if a CFG is in CNF and if there is a constraint on the use of live output at most once each, then it is only possible to produce finite words.It must be noted that it increases the number of nonterminals by one each time a live output is applied during the derivation of a name. Similarly, the application of dead manufacturing reduces the nonterminals by one. Which indicates that one more dead production is applied to produce a word than live productions e.g. One live and two dead productions are presented here. In general, if a CFG has p live and q dead productions in CNF, then at most (p+1) letters are all words produced without repeating any live output.

Sign Up