To construct a parse tree for the expression (x1 + x2 / x1) * (x1 * x2 + x2), a context-free grammar defining the arithmetic operations with precedence rules is applied. Start with the production rule for expressions E; for multiplication, use E → E * E, and for addition/subtraction, use E → E + E | E - E. For factor, use F for terms inside parentheses: E → (E) or terminals as identifiers: E → x1 | x2. The parse tree begins at the root with the operation *, having two branches for the sub-expressions (x1 + x2 / x1) and (x1 * x2 + x2), each further broken down into their respective operator and parenthesized components, creating nodes for each operation and identifier.

Converting a CFG into Chomsky Normal Form (CNF) involves several steps: removing ε-productions, removing unit productions, eliminating useless symbols, and replacing productions with longer right-hand sides. For the given CFG R = {S → AbA | B, A → a | ε, B → a | b}, the conversion proceeds as follows: 1) Remove ε-productions by modifying rules and adding alternative paths for derivations that include ε, 2) Remove unit productions such as S → B by directly replacing B's productions in S, and 3) Break down productions with more than two symbols on the right-hand side into binary productions. The resulting CNF could be: S → X1A | B, X1 → aA, A → a, B → a | b, where X1 is an introduced variable to create binary productions.

A context-free grammar (CFG) is a type of formal grammar that is used to generate all possible strings in a given context-free language. For the language L = {a^n b^n : n ≥ 0}, a CFG can be constructed using the production rule S → aSb | ε. This rule ensures that for every 'a' added to the string, a corresponding 'b' is added, ultimately making the number of 'a's equal to the number of 'b's. The string 'aabb' is derived in this CFG with the leftmost derivation: S → aSb → aaSbb → ε. The rightmost derivation would be S → aSb → aabSb → aabb. A parse tree demonstrates these derivations by showing the hierarchical structure of applying the production rules, where 'aabb' emerges from the initial symbol S.

A PDA for L = {w: w ∈ {a, b}*, #a = #b} can use a stack to count the number of 'a's and 'b's. The PDA pushes onto the stack for each 'a' seen and pops for each 'b' seen. The PDA starts in an initial state q0, moves to a state q1 with an ε-transition that simulates checking stack emptiness at the end. In state q1, it checks if the stack is empty upon finishing the input to ensure equal 'a's and 'b's. For the string 'abab', the PDA will 1) Push 'a' onto the stack when reading 'a', and 2) Pop the stack when reading 'b'. If at the end, the stack is empty, the string is accepted by the PDA.

To analyze whether L = {a^n b^2n : n ≥ 0} is a context-free language, apply the pumping lemma for context-free languages. Assume L is context-free. Then, there exists a pumping length p such that any string s in L with |s| ≥ p can be divided into uvwxy with |vwx| ≤ p, |vx| > 0, and uv^iwx^iy ∈ L for i ≥ 0. Consider s = a^p b^{2p}. Since |vwx| ≤ p, vwx consists entirely of 'a's or of 'b's but not both. If vwx contains only 'a's, pumping results in unequal numbers of 'a's and 'b's. If it contains only twice as many 'b's, pumping i ≠ 1 alters the 2-to-1 ratio, thus violating L's constraints. Thus, L cannot be context-free, proving a contradiction to the pumping lemma assumption.

The intersection of L1 = {a^i b^j c^k: i = j} and L2 = {a^i b^j c^k: j = k}, denoted as L1 ∩ L2, consists of strings where i = j = k. This language is equivalent to L = {a^n b^n c^n: n ≥ 0}. Using the pumping lemma, L can be shown not to be context-free because no matter how the string a^n b^n c^n (with n sufficiently large) is divided into uvwxy having |vwx| ≤ p (pumping length), pumping v and x does not maintain the form a^n b^n c^n for i ≠ 1. Therefore, L1 ∩ L2 is not context-free due to the unique equal number constraint across three types of symbols.

An ambiguous grammar is one where a single string can have multiple distinct parse trees or derivations. The grammar R = {S → 0A | 1B, A → 0AA | 1S | 1, B → 1BB | 0S | 0} is considered ambiguous because there exist certain strings—such as '0011'—that can be derived in more than one way. For example, '0011' can be derived using the rule S → 0A → 00AA → 001S → 0011 and alternatively as S → 0A → 01S → 0111. The existence of multiple valid parse trees indicates the grammar is ambiguous.

The language L = {0^n 1^2n 0^n : n > 0} is examined for context-freedom using the Pumping Lemma for context-free languages. Assume L is context-free with pumping length p. Consider the string s = 0^p 1^2p 0^p in L. According to the pumping lemma, s can be divided into uvwxy with |vwx| ≤ p and |vx| > 0 such that uv^iwx^iy is in L for all i ≥ 0. The division of '0^p' into vwx cannot keep both halves balanced when pumped, as any inclusion of 1^2p shifted results in disproportionate counts of zeros on either side of the ones, violating L's structure. Thus L is not context-free, contradicting the assumption and proving the lemma.

Context-free languages are closed under concatenation because given two context-free grammars G1 for language L1 and G2 for language L2, a new grammar G3 can construct strings by concatenating derivations of G1's strings with those of G2, thus forming strings in L1L2. However, context-free languages are not closed under complementation because the complement of a CFL is not necessarily a CFL. For instance, the complement of the language {a^n b^n : n ≥ 0}, which is context-free, requires keeping track of unequal numbers of 'a's and 'b's, something a PDA (the device associated with CFGs) cannot handle due to its limited stack capability.

The language L = {ww: w ∈ {a, b}*} can be shown to be non-context-free using the pumping lemma. Assume it is context-free, identifying a pumping length p. Consider the string s = a^p b^p a^p b^p, clearly in L. This string s must be decomposed as uvwxy, where |vwx| ≤ p and |vx| > 0. The substring vwx will only include a portion of one or both of the repeated segments. When pumping i ≠ 1, the repetition within some 'aa' or 'bb' segments causes the second half of the string not to match the first, thus violating the form of ww, contradicting the pumping lemma. Hence, L is not context-free.