Show that the language L = {awwR: w ∈ {a, b}*} is context-free.

 Show that the language L = {awwR: w ∈ {a, b}*} is context-free.

Answer-

A language is context free language if it is generated by context free grammar. Therefore we generate grammar for given language. If grammar generated by language is context free grammar then given language will be context free language. 

Explanation

A language is context free language if it is generated by context free grammar. Therefore we generate grammar for given language. If grammar generated by language is context free grammar then given language will be context free language. 

Language L = {awwR: w ∈ {a, b}*} is context-free.

Grammar for language(L)-

Grammar(G) = (V, Σ, P, S) 

Where 

V = {S,A}

Σ = {a, b},
P = { S→ aA , A → aAa , A → bAb , A →ε }

S={S} Starting symbol of grammar.

Context free grammar-

A grammar(G) is context free grammar if it is defined as

G = (V, Σ, P, S)

where 

V= is a set of non-terminal symbols.

Σ= is a set of terminals

P= Production rule P: V → (V ∪ Σ)*

S=is the start symbol

According to definition of context free grammar the generated grammar (G) by language(L) is context free grammar. Hence language L = {awwR: w ∈ {a, b}*} is context-free.

Comments

Post a Comment

Popular posts from this blog

The python program allows the user to enter the Sales amount and Actual cost of a Product. Next, Python calculates the Loss Amount or profit Amount based on those two values using if-elif-else Statement

Image
  Write Pseudocode and draw flow chart of the following problem . The python program allows the user to enter the Sales amount and Actual cost of a Product. Next, Python calculates the Loss Amount or profit Amount based on those two values using if-elif-else Statement. Answer- Pseudocode Input the Actual cost of  Product Input the Sales Amount if(actual_cost > sale_amount):     amount = actual_cost - sale_amount     print("Total Loss Amount") elif(sale_amount > actual_cost):     amount = sale_amount - actual_cost     print("Total Profit ") else:     print("No Profit No Loss!!!") Flow chart- Python Code- #Input Actual cost of  Product actual_cost = float(input(" Please Enter the Actual cost of  Product:")) # Input Sales Amount sale_amount = float(input(" Please Enter the Sales Amount: ")) #calculate Loss Amount if(actual_cost > sale_amount):     amount = actual_cost - sale_amount     print("Total Loss Amount = {0}".for
Read more

Mealy and Moore Machine

 Mealy Machine – A mealy machine is defined as 6 tuples (Q, q0, ∑, Δ, δ, λ’)  Q - finite non empty set of states  q0 - initial state  ∑-  input alphabet or terminals  Δ - output alphabet  δ - transition function δ:Q×∑ → Q  λ - output function λ: Q×∑→ O  Moore Machine – A moore machine is defined as 6 tuples (Q, q0, ∑, Δ, δ, λ’)  Q - finite non empty set of states  q0 - initial state  ∑-  input alphabet or terminals  Δ - output alphabet  δ - transition function δ:Q×∑ → Q  λ - output function λ: Q→O  1. Moore Machine is : a) FA without input b) FA with output c) NDFA with input d) None of the above Answer: b Explanation: Finite automaton with an output is  categorized in two parts: Moore M/C and Mealy M/C. 2.Which of the following is uesd as  output alphabet  in moore machine? a) δ b) ∆ c) ∑ d) None of the above Answer-b 3.Which of the following produce output for moore machine?  a) λ: Q→O b) λ: Q×∑→ O c) both a and b d) none of the above 4.The Output of Moore machine depends on a) only
Read more

Context free grammar

  Question: Answer each part for the following context-free grammar G. R → XRX | S S → aT b | bT a T → XT X | X | ε X → a | b very important : if you know how to answer these questions. leave your email and i will contact you or come here at 5 pm (new york time) you will answer similar questions. the point of asking this question is to be able to connect with someone who knows the topic a. What are the variables of G? b. What are the terminals of G? c. Which is the start variable of G? d. Give three strings in L(G). e. Give three strings not in L(G). f. True or False: T ⇒ aba. g. True or False: T ∗⇒ aba. h. True or False: T ⇒ T . i. True or False: T ∗⇒ T . j. True or False: XXX ∗⇒ aba. k. True or False: X ∗⇒ aba. l. True or False: T ∗⇒ XX. m. True or False: T ∗⇒ XXX. n. True or False: S ∗⇒ ε. o. Give a description in English of L(G). Answer Answer-a) Variables of grammar(G)-(R,X,S,T) Answer-b) Terminals of grammar(G)-{a,b} Answer-c) Starting variable of grammar(G)-{R} Answer-d) Three s
Read more